Detailed mathematical approach

Problem Summary

The task is to count decimal palindromes of length at most \(32\) that are divisible by \(10{,}000{,}019\). More generally, the implementation solves the same counting problem for any modulus \(M\) and any maximum length \(n\), then evaluates it at \(M=10{,}000{,}019\) and \(n=32\).

If \(A_{\ell}(M)\) denotes the number of length-\(\ell\) palindromes divisible by \(M\), the required quantity is

$\sum_{\ell=1}^{32} A_{\ell}(10{,}000{,}019).$

A direct enumeration is still enormous, because even after using palindrome symmetry there are \(9\cdot 10^{15}\) possible 32-digit half-assignments. The solution therefore rewrites each palindrome as a modular linear form in its independent digits and counts matching residues with a meet-in-the-middle split.

Mathematical Approach

Fix a length \(\ell\) and a modulus \(M\). Let

$h=\left\lceil\frac{\ell}{2}\right\rceil.$

A palindrome of length \(\ell\) is determined by exactly \(h\) independent digits, so the question becomes: how many assignments of those digits make the resulting number congruent to \(0\pmod M\)?

Step 1: Encode a palindrome by mirrored digit weights

Number decimal positions from the right, starting at \(0\). For each \(0\le i<h\), let \(d_i\) be the digit placed simultaneously at positions \(i\) and \(\ell-1-i\). If \(\ell\) is odd and \(i=\ell-1-i\), that digit is the center and contributes only once.

Because the highest place \(\ell-1\) belongs to the pair indexed by \(i=0\), the digit \(d_0\) is the leading digit, so

$d_0\in\{1,\dots,9\},\qquad d_1,\dots,d_{h-1}\in\{0,\dots,9\}.$

The palindrome value modulo \(M\) is therefore

$P_{\ell}(d_0,\dots,d_{h-1})\equiv \sum_{i=0}^{h-1} d_i W_i \pmod M,$

with mirrored weights

$W_i=\begin{cases} 10^i+10^{\ell-1-i}\pmod M, & i\ne \ell-1-i,\\ 10^i\pmod M, & i=\ell-1-i. \end{cases}$

So divisibility becomes one linear congruence in the independent digits.

Step 2: Split the independent digits into two balanced blocks

Choose

$s=\left\lceil\frac{h}{2}\right\rceil.$

The left block contains \(d_0,\dots,d_{s-1}\), and the right block contains \(d_s,\dots,d_{h-1}\). Define

$L=\sum_{i=0}^{s-1} d_i W_i \pmod M,\qquad R=\sum_{i=s}^{h-1} d_i W_i \pmod M.$

Then

$P_{\ell}\equiv L+R\pmod M,$

so a palindrome is divisible by \(M\) exactly when

$L+R\equiv 0\pmod M.$

This turns the problem into matching left residues against complementary right residues.

Step 3: Count all possible left residues once

The leading-digit restriction affects only \(d_0\). It is therefore natural to separate the leading digit from the remaining \(s-1\) digits in the left block. For each fixed \(a\in\{1,\dots,9\}\), the other left digits vary freely in \(\{0,\dots,9\}^{s-1}\).

If we define

$C_{\ell}(r)=\#\{(d_0,\dots,d_{s-1}) : L\equiv r\pmod M\},$

then \(C_{\ell}(r)\) records how many left-half assignments produce residue \(r\). Once this frequency table has been built for the current length, it can be reused for every right-half assignment.

Step 4: Match complementary right residues

Now enumerate all assignments of the right block. Each one gives some residue \(R\). The divisibility condition requires

$L\equiv -R\pmod M.$

Hence the number of full palindromes extending that right block is exactly

$C_{\ell}((-R)\bmod M).$

Summing this quantity over all right-half assignments yields \(A_{\ell}(M)\). Finally, summing \(A_{\ell}(M)\) over \(\ell=1,\dots,32\) gives the answer required by the problem.

Step 5: Why the split changes the scale of the search

Without the split, a length-\(\ell\) palindrome requires checking \(9\cdot 10^{h-1}\) independent digit assignments. With the balanced split above, the left side contributes \(9\cdot 10^{s-1}\) assignments and the right side contributes \(10^{h-s}\) assignments.

For the longest case \(\ell=32\), we have \(h=16\) and \(s=8\), so the method works with roughly \(9\cdot 10^7\) left assignments and \(10^8\) right assignments instead of \(9\cdot 10^{15}\) full half-assignments. That reduction is the reason the computation becomes feasible.

Worked Example: \(M=109\) and \(\ell=5\)

For length \(5\), we have \(h=3\) and \(s=2\). The mirrored weights are

$W_0=10^0+10^4\equiv 1+81\equiv 82\pmod{109},$

$W_1=10^1+10^3\equiv 10+19\equiv 29\pmod{109},$

$W_2=10^2\equiv 100\pmod{109}.$

So every 5-digit palindrome has residue

$P_5(a,b,c)\equiv 82a+29b+100c\pmod{109},$

with \(a\in\{1,\dots,9\}\) and \(b,c\in\{0,\dots,9\}\). The left table counts residues of \(82a+29b\), while the right side enumerates residues of \(100c\).

Since \(100\equiv -9\pmod{109}\), the left-table queries are the complementary residues \(0,9,18,\dots,81\) as \(c\) runs from \(0\) to \(9\). This illustrates the whole strategy in miniature. The implementations also include the checkpoint that the cumulative count for lengths \(1\) through \(5\) at modulus \(109\) is \(9\).

How the Code Works

The implementation first precomputes the powers \(10^i\bmod M\) up to the largest decimal position needed. For each length \(\ell\), it constructs the mirrored weights \(W_i\), chooses the balanced split \(s=\lceil h/2\rceil\), and prepares a frequency table for left-block residues.

To build that table efficiently, it enumerates the non-leading part of the left block once, records those residues, and then combines them with each possible leading digit \(1\) through \(9\). After that, it enumerates all right-block assignments and adds the frequency of the complementary left residue required for divisibility.

Two implementation details matter for speed. First, the digit blocks are traversed in base-10 counter order while maintaining the current residue incrementally, so moving to the next assignment updates only the digits that changed. Second, after one length is finished, only residue classes that actually received counts are cleared; the whole size-\(M\) table is never reset blindly.

The C++, Python, and Java implementations follow the same mathematics. The Python entry point delegates the heavy arithmetic to compiled code, while the Java version reproduces the same residue-counting procedure directly.

Complexity Analysis

For one length \(\ell\), let \(h=\lceil \ell/2\rceil\) and \(s=\lceil h/2\rceil\). Building the mirrored weights costs \(O(h)\). The left-side preparation touches \(10^{s-1}\) assignments for the non-leading digits and then combines them with \(9\) possible leading digits, while the right side touches \(10^{h-s}\) assignments.

The dominant work per length is therefore

$O\left(10^{s-1}+9\cdot 10^{s-1}+10^{h-s}\right)=O\left(10^{s}+10^{h-s}\right).$

With the balanced split, this is essentially \(O(10^{\lceil h/2\rceil})\). Memory usage is

$O\left(M+10^{s-1}\right),$

coming from the residue-frequency table indexed by modulo classes and from the stored residues of the non-leading part of the left block. Across all lengths up to \(32\), the longest lengths dominate the total running time.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=655
2. Palindromic number: Wikipedia — Palindromic number
3. Modular arithmetic: Wikipedia — Modular arithmetic
4. Positional notation: Wikipedia — Positional notation
5. Meet-in-the-middle technique: Wikipedia — Meet-in-the-middle attack