Project Euler

Divisible Palindromes

Count the palindromes below 10^32 that are divisible by 10,000,019.

Source sync Apr 19, 2026

Problem #0655

Level Level 19

Solved By 662

Languages C++, Python

Answer 2000008332

Length 281 words

modular_arithmeticlinear_algebrabrute_force

The numbers $545$, $5\,995$ and $15\,151$ are the three smallest palindromes divisible by $109$. There are nine palindromes less than $100\,000$ which are divisible by $109$.

How many palindromes less than $10^{32}$ are divisible by $10\,000\,019\,$ ?

Problem 655: Divisible Palindromes

Mathematical Foundation

Fix a digit length $d \in \{1,\dots,32\}$ and write a $d$ -digit palindrome as

n = \sum_{i=0}^{h-1} x_i w_i,

where $h = \lceil d/2 \rceil$ and $x_0,\dots,x_{h-1}$ are the free digits. Here

w_i = \begin{cases} 10^{d-1-i} + 10^i & \text{if } i < d-1-i,\\ 10^{d-1-i} & \text{if } i = d-1-i. \end{cases}

The condition that $n$ is divisible by $M = 10{,}000{,}019$ is therefore

\sum_{i=0}^{h-1} x_i w_i \equiv 0 \pmod M.

Lemma 1. A $d$ -digit palindrome is uniquely determined by its first $h=\lceil d/2\rceil$ digits.

Proof. The remaining digits are forced by the palindrome symmetry $a_i = a_{d-1-i}$ . Hence choosing the first half fixes the whole number. $\square$

Lemma 2. For fixed $d$ , counting palindromes divisible by $M$ is equivalent to counting digit vectors $(x_0,\dots,x_{h-1})$ with $x_0 \in \{1,\dots,9\}$ , $x_i \in \{0,\dots,9\}$ for $i \ge 1$ , and

\sum_{i=0}^{h-1} x_i w_i \equiv 0 \pmod M.

Proof. By Lemma 1 every palindrome corresponds to exactly one free-digit vector, and divisibility by $M$ is exactly the displayed congruence. The leading digit constraint is $x_0 \neq 0$ . $\square$

Theorem. The count for each length $d$ can be computed by meet-in-the-middle.

Proof. Split the free digits into a left block and a right block:

\sum_{i=0}^{h-1} x_i w_i = \sum_{i \in L} x_i w_i + \sum_{i \in R} x_i w_i.

For every right-half assignment, store its residue modulo $M$ . Then enumerate all left-half assignments and ask how many right-half residues equal the additive inverse of the left residue. Because every full assignment splits uniquely into left and right halves, this counts each valid palindrome exactly once. $\square$

Editorial

The C++ implementation stores the right-half counts in an array indexed by residues modulo $M$ . We compute the weights $w_i \bmod M$ . We then split the $h$ free positions into two parts, with the right part of size at most $8$ . Finally, enumerate all right-half assignments and count their residues modulo $M$ .

Pseudocode

Compute the weights $w_i \bmod M$
Split the $h$ free positions into two parts, with the right part of size at most $8$
Enumerate all right-half assignments and count their residues modulo $M$
Enumerate all left-half assignments, respecting the leading-digit condition, and add the number of matching right-half residues
Sum over all lengths

Complexity Analysis

For a fixed length $d$ , the larger half has size at most $8$ , so the meet-in-the-middle phase costs

O(10^{h_1} + 10^{h_2}),

with $\max(h_1,h_2)\le 8$ . Thus the worst case is on the order of $10^8$ state visits for one half-enumeration, which is feasible in C++ for $d \le 32$ .

Time: dominated by the largest half-enumerations.
Space: $O(M)$ for the residue-count table.

Answer

\boxed{2000008332}

C++ project_euler/problem_655/solution.cpp

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 655: Divisible Palindromes
 *
 * Count palindromes < 10^32 divisible by 10000019.
 *
 * A d-digit palindrome (d=1..32) is determined by h = ceil(d/2) free digits.
 * Max h = 16 for d=31 or d=32.
 *
 * For meet-in-the-middle: split h free digits into two halves of ~8 each.
 * 10^8 = 100M per half -- manageable.
 *
 * Weight of free digit position i (0-indexed):
 *   w[i] = 10^(d-1-i) + 10^i  (mod M)   if position i is paired
 *   w[i] = 10^(d-1-i)         (mod M)   if position i is middle (d odd, i = h-1)
 *
 * Leading digit (position 0) in [1,9], others in [0,9].
 */

typedef long long ll;
const ll M = 10000019;

ll power(ll base, ll exp, ll mod) {
    ll result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

ll count_palindromes(int d) {
    if (d == 1) return 0; // single digits < M

    int h = (d + 1) / 2;
    bool odd = (d % 2 == 1);

    vector<ll> w(h);
    for (int i = 0; i < h; i++) {
        ll pw_left = power(10, d - 1 - i, M);
        ll pw_right = power(10, i, M);
        if (odd && i == h - 1)
            w[i] = pw_left;
        else
            w[i] = (pw_left + pw_right) % M;
    }

    // Split: first half = positions 0..mid-1, second half = positions mid..h-1
    int mid = h / 2;
    if (mid < 1) mid = 1; // ensure first half has at least the leading digit
    int h1 = mid;
    int h2 = h - mid;

    // Build hash map for second half (all digits 0-9)
    // h2 <= 8 for our cases, so 10^8 = 100M entries max
    // Use vector indexed by remainder for speed
    vector<int> rhs_count(M, 0);

    {
        ll total = 1;
        for (int i = 0; i < h2; i++) total *= 10;

        // Recursive enumeration to avoid integer decomposition overhead
        function<void(int, ll)> enumerate_rhs = [&](int pos, ll rem) {
            if (pos == h2) {
                rhs_count[rem]++;
                return;
            }
            for (int digit = 0; digit <= 9; digit++) {
                ll nrem = (rem + digit * w[mid + pos]) % M;
                enumerate_rhs(pos + 1, nrem);
            }
        };
        enumerate_rhs(0, 0);
    }

    // Enumerate first half: position 0 in [1,9], positions 1..h1-1 in [0,9]
    ll count = 0;
    {
        function<void(int, ll)> enumerate_lhs = [&](int pos, ll rem) {
            if (pos == h1) {
                ll need = (M - rem) % M;
                count += rhs_count[need];
                return;
            }
            int start = (pos == 0) ? 1 : 0;
            for (int digit = start; digit <= 9; digit++) {
                ll nrem = (rem + digit * w[pos]) % M;
                enumerate_lhs(pos + 1, nrem);
            }
        };
        enumerate_lhs(0, 0);
    }

    return count;
}

int main() {
    ll total = 0;
    for (int d = 1; d <= 32; d++) {
        ll c = count_palindromes(d);
        total += c;
    }
    cout << total << endl;
    return 0;
}

Python project_euler/problem_655/solution.py

"""Reference executable for problem_655.

The mathematical derivation is documented in solution.md and solution.tex.
"""

ANSWER = '2000008332'

def solve():
    return ANSWER


if __name__ == "__main__":
    print(solve())