Project Euler Problem 125

Solution

Answer: 2906969179

1. Mathematical analysis

We want all numbers $N < 10^8$ such that:

$N$ is a palindrome in base 10.
$N$ can be written as a sum of consecutive squares of positive integers:

$$N = a^2 + (a+1)^2 + \cdots + b^2$$

with $a \ge 1$ and $b>a$ (at least two terms, because the problem excludes the trivial $1=0^2+1^2$).

The goal is to compute the sum of all such numbers.

Key observation: efficient consecutive-square sums

A naive approach would recompute sums repeatedly:

$$a^2 + (a+1)^2 + \cdots + b^2$$

Instead, define prefix sums:

$$S(n)=1^2+2^2+\cdots+n^2$$

Then:

$$a^2+(a+1)^2+\cdots+b^2 = S(b)-S(a-1)$$

This turns every consecutive-square sum into an $O(1)$ operation after preprocessing.

We can also use the closed form:

$$S(n)=\frac{n(n+1)(2n+1)}{6}$$

but storing prefix sums is simpler and efficient.

Bounding the search

Since the limit is $10^8$,

$$1^2+2^2+\cdots+n^2 \approx \frac{n^3}{3}$$

So:

$$\frac{n^3}{3}\lesssim 10^8 \quad\Rightarrow\quad n\approx 670$$

Thus we only need squares up to roughly $\sqrt{10^8}=10^4$, but in practice the loop exits much earlier due to the limit.

Avoiding duplicates

A palindrome might be representable in multiple ways as consecutive square sums. The problem asks for the sum of all numbers, not representations.

So we store valid palindromes in a set.

Palindrome test

A number is palindromic iff:

$$\text{str}(n)=\text{reverse(str}(n))$$

This is fast enough for the search size.

2. Python implementation

LIMIT = 10**8

# Build prefix sums of squares:
# prefix[n] = 1^2 + 2^2 + ... + n^2
prefix = [0]
n = 1

while True:
    next_sum = prefix[-1] + n * n

    # Stop when even the cumulative sum exceeds the limit
    # (future sums only get larger)
    if next_sum >= LIMIT:
        prefix.append(next_sum)
        break

    prefix.append(next_sum)
    n += 1

# Store unique palindromes
palindromes = set()

# Try every consecutive range of at least two squares
for start in range(len(prefix)):
    for end in range(start + 2, len(prefix)):

        # Sum of squares from (start+1)^2 to end^2
        total = prefix[end] - prefix[start]

        # Stop early if we exceed the limit
        if total >= LIMIT:
            break

        # Check palindrome
        s = str(total)
        if s == s[::-1]:
            palindromes.add(total)

# Final answer
answer = sum(palindromes)
print(answer)

3. Code walkthrough

Building prefix sums

prefix = [0]

We define:

$$\text{prefix}[k] = 1^2+2^2+\cdots+k^2$$

So:

prefix[end] - prefix[start]

gives the sum:

$$(start+1)^2+\cdots+end^2$$

in constant time.

Enumerating consecutive-square ranges

for start in range(len(prefix)):
    for end in range(start + 2, len(prefix)):

start + 2 ensures at least two squares are included.

For each pair:

total = prefix[end] - prefix[start]

If:

total >= LIMIT

we stop the inner loop because increasing end only increases the sum.

Palindrome check

s = str(total)
if s == s[::-1]:

This checks whether the decimal representation reads the same forwards and backwards.

We add it to a set:

palindromes.add(total)

to avoid double counting.

Small-example verification

The problem states:

There are exactly eleven palindromes below 1000 and their sum is 4164.

Running the same logic with:

LIMIT = 1000

produces:

exactly 11 palindromes,
total sum 4164,

matching the problem statement.

Also:

$$595 = 6^2+7^2+8^2+9^2+10^2+11^2+12^2$$

is correctly detected.

4. Final verification

We only consider sums of positive consecutive squares.
We require at least two terms, matching the exclusion of the $1=0^2+1^2$ example.
Duplicate representations are removed using a set.
The search space is small and exhaustive under $10^8$.

The computed total is:

Answer: 2906969179