Detailed mathematical approach

Problem Summary

For each \(n\), let \(A(n)\) be the number of binary strings of length \(n\) that avoid every palindromic substring of length at least \(5\). Then the number of length-\(n\) strings that do contain such a palindrome is \(2^n-A(n)\), and the cumulative function is

$F_5(n)=\sum_{k=1}^{n}\left(2^k-A(k)\right).$

The required counting function is

$D(L)=\#\left\{n\in\mathbb{Z}:5\le n\le L,\ F_5(n)\equiv 0 \pmod{87654321}\right\}.$

With \(L=10^{18}\), direct enumeration is hopeless. The implementations instead convert the problem into a periodic congruence in one auxiliary variable.

Mathematical Approach

The solution first counts palindrome-avoiding strings of one exact length, then turns that count into a closed form for \(F_5(n)\), and finally solves a modular periodicity problem.

Step 1: Reduce the Forbidden Patterns to Lengths 5 and 6

A binary string contains a palindrome of length at least \(5\) if and only if it contains a palindrome of length exactly \(5\) or exactly \(6\).

Every odd palindrome of length at least \(5\) has a centered palindrome of length \(5\), and every even palindrome of length at least \(6\) has a centered palindrome of length \(6\). So the avoidance problem is equivalent to forbidding only these two local patterns.

Step 2: Count Exact-Length Avoiders with a Finite-State DP

Let \(A(n)\) be the number of valid length-\(n\) strings. When a new bit \(x\) is appended, only suffixes ending at that new bit can create a new forbidden palindrome, so it is enough to remember the last five bits.

If the previous suffix is \(b_1b_2b_3b_4b_5\), then appending \(x\) creates a forbidden palindrome of length \(5\) exactly when

$b_2=x \land b_3=b_5,$

and it creates one of length \(6\) exactly when

$b_1=x \land b_2=b_5 \land b_3=b_4.$

So after length \(5\), the process is a DP on at most \(32\) suffix states. The exact totals begin as

$A(5)=24,\quad A(6)=30,\quad A(7)=32,\quad A(8)=32,$

and from \(n=9\) onward the totals enter a stable period of length \(6\):

$A(9+6t+u)=a_u,\qquad (a_0,a_1,a_2,a_3,a_4,a_5)=(32,34,36,34,32,32).$

One complete six-step block therefore contributes

$a_0+a_1+a_2+a_3+a_4+a_5=200.$

Step 3: Sum Those Exact Counts to Obtain \(F_5(n)\)

There are \(2^n\) binary strings of length \(n\), so the number that contain a qualifying palindrome is \(2^n-A(n)\). Summing over all lengths gives

$F_5(n)=\sum_{k=1}^{n}\left(2^k-A(k)\right)=(2^{n+1}-2)-\sum_{k=1}^{n}A(k).$

Write

$n=9+6t+u,\qquad u\in\{0,1,2,3,4,5\}.$

Because the exact-length avoidance counts are periodic, their cumulative sum is linear in \(t\):

$\sum_{k=1}^{9+6t+u}A(k)=200t+(C_u-2),$

with

$\left(C_0,C_1,C_2,C_3,C_4,C_5\right)=\left(182,216,252,286,318,350\right).$

Substituting into the previous identity yields the closed form used by all three implementations:

$F_5(9+6t+u)=2^{10+u}64^t-(200t+C_u).$

Step 4: Turn Divisibility into a Congruence in \(t\)

The target condition is \(F_5(n)\equiv 0 \pmod{87654321}\). For fixed \(u\), the closed form becomes

$2^{10+u}64^t \equiv 200t+C_u \pmod{87654321}.$

The modulus factors as

$87654321=9\cdot 1997\cdot 4877.$

So the implementations solve the congruence modulo \(9\), \(1997\), and \(4877\) separately. For one modulus \(m\), the exponential factor \(64^t\) has period \(\operatorname{ord}_m(64)\), while the linear term \(200t+C_u\) has period \(m\). Hence the local period is

$P_m=\operatorname{lcm}\left(m,\operatorname{ord}_m(64)\right).$

In this problem the three local periods are

$P_9=9,\qquad P_{1997}=1993006,\qquad P_{4877}=11890126.$

Step 5: Merge Local Residues with the Chinese Remainder Theorem

For each fixed \(u\), the implementation enumerates one full local period for each modulus factor and records every residue \(t\) that satisfies the congruence modulo that factor.

Two congruences

$x\equiv a \pmod{m_1},\qquad x\equiv b \pmod{m_2}$

are compatible exactly when

$a\equiv b \pmod{\gcd(m_1,m_2)}.$

Compatible residues are merged step by step into global residues modulo

$P=\operatorname{lcm}(P_9,P_{1997},P_{4877}).$

The important point is that the code never scans all \(P\) residue classes. It scans only the three local periods above and combines the matching classes constructively by CRT.

Worked Example

Take \(n=11\). Then \(n=9+6\cdot 0+2\), so \(t=0\) and \(u=2\). The closed form gives

$F_5(11)=2^{12}-252=3844.$

This matches the exact avoidance counts. Up to length \(11\), the valid-string totals are

$A(1),\dots,A(11)=2,4,8,16,24,30,32,32,32,34,36,$

so

$\sum_{k=1}^{11}A(k)=250,$

and therefore

$F_5(11)=(2^{12}-2)-250=4094-250=3844.$

Now move one full six-step block forward to \(n=17\). The avoidance sum grows by another \(200\), so

$F_5(17)=2^{18}-(200+252)=261692.$

This illustrates why large \(n\) are naturally parameterized by the pair \((t,u)\).

How the Code Works

The C++, Python, and Java implementations begin with a small finite-state DP over the last up to five bits. That DP produces the exact short values, including the checkpoints \(F_5(5)=8\), \(F_5(6)=42\), and \(F_5(11)=3844\), and it also confirms the six-term avoidance cycle used by the closed form.

Next, for every \(u\in\{0,1,2,3,4,5\}\) and every modulus factor \(m\in\{9,1997,4877\}\), the implementation scans one local period \(P_m\) and records the residues satisfying

$2^{10+u}64^t \equiv 200t+C_u \pmod m.$

Those local residue sets are merged with CRT into sorted global residue lists. For a query limit \(L\), the code handles \(n=5,6,7,8\) directly and, for each \(u\), counts how many

$t\le \left\lfloor\frac{L-(9+u)}{6}\right\rfloor$

fall into the stored global residue classes. With sorted residues, the final count is computed as full periods plus a tail found by binary search.

Complexity Analysis

Let \(R_{m,u}\) be the number of valid residues for modulus factor \(m\) in class \(u\). The local scans cost

$O\left(\sum_{u=0}^{5}\left(P_9+P_{1997}+P_{4877}\right)\right),$

which is a one-time preprocessing step independent of \(L\). The CRT phase depends on the residue-set sizes, not on the enormous global period \(P\). After preprocessing, evaluating \(D(L)\) only requires six limit conversions and counts in sorted arrays, so the dependence on \(L\) is effectively \(O(1)\) with small logarithmic factors from binary search. Memory usage is proportional to the total number of stored residue classes.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=486
2. Palindrome: Wikipedia — Palindrome
3. Chinese remainder theorem: Wikipedia — Chinese remainder theorem
4. Multiplicative order: Wikipedia — Multiplicative order
5. Finite-state machine: Wikipedia — Finite-state machine