Project Euler Problem 486
Let F5(n) be the number of strings s such that: - s consists only of '0's and '1's, - s has length at most n, and - s co
Solution
Answer: 11408450515
Let $A(n)$ be the number of binary strings of length exactly $n$ avoiding any palindromic substring of length at least $5$. Then
$$F_5(n)=\sum_{k=1}^{n} \left(2^k-A(k)\right).$$
The key observation is:
Any palindrome of length $\ge 5$ contains a palindrome of length $5$ or $6$.
So avoiding all palindromes of length $\ge 5$ is equivalent to forbidding only length-5 and length-6 palindromes.
A finite automaton on the last 5 bits gives the exact counts $A(n)$. Computing a short prefix reveals that for $n\ge 7$, the sequence becomes periodic:
$$A(n)= (32,32,32,34,36,34) \quad\text{repeating with period }6.$$
Summing this yields a closed form for $F_5(n)$. Writing
$$n=6q+s,\qquad s\in{1,2,3,4,5,6},$$
one gets congruences of the form
$$2^{n+1} - 2 - A_{\le n} \equiv 0 \pmod{87654321}.$$
Since $87654321=3^2\cdot1997\cdot4877$, the problem reduces via CRT to solving periodic congruences in $q$. The full solution set is periodic with period
$$\operatorname{lcm}!\bigl(87654321,\operatorname{ord}_{87654321}(64)\bigr) = 106636916064402.$$
Counting all admissible residue classes up to $10^{18}$ reproduces the checks
$$D(10^7)=0, \qquad D(5\cdot10^9)=51,$$
and finally gives:
Answer: 11408450515