Detailed mathematical approach

Problem Summary

We seek every palindromic integer \(n<10^8\) that can be written as a sum of consecutive positive squares with at least two terms:

$n=a^2+(a+1)^2+\cdots+b^2,\qquad 1\le a<b.$

The final answer is the sum of those palindromic values, not the number of representations. That distinction matters because the same palindrome may arise from more than one interval of consecutive squares, so valid values must be counted only once.

Mathematical Approach

The implementations do not search blindly. They convert every consecutive-square sum into a difference of square-prefix totals, use monotonic growth to stop each search branch as soon as it becomes too large, and store successful palindromes in a set so repeated representations do not change the final total.

Interval sums from square-prefix totals

Define the prefix sum of squares

$P_n=\sum_{k=1}^{n} k^2=\frac{n(n+1)(2n+1)}{6}.$

Then every block of consecutive squares from \(a\) through \(b\) can be written as

$S(a,b)=\sum_{k=a}^{b} k^2=P_b-P_{a-1}=\frac{b(b+1)(2b+1)-(a-1)a(2a-1)}{6}.$

This is the central algebraic object of the problem. Once the prefix totals are known, the sum for any interval \([a,b]\) is obtained in constant time from one subtraction instead of recomputing every square inside that interval.

Why the search space is finite

If a consecutive-square sum is below \(10^8\), then in particular its largest term satisfies \(b^2<10^8\). Hence \(b<10^4\), so only starting and ending values up to the square-root scale of the limit ever matter.

There is also a stronger bound on the starting point. Because the interval must contain at least two terms, the smallest admissible sum beginning at \(a\) is

$a^2+(a+1)^2=2a^2+2a+1.$

If this already exceeds the limit, then no larger end point can rescue that start. Solving \(2a^2+2a+1<10^8\) shows that starts beyond roughly \(7070\) are mathematically impossible. The implementations use the simpler safe ceiling near \(\sqrt{10^8}\) when building the prefix table, and the later monotonic break discards the impossible tails automatically.

Monotonicity in the right endpoint

For a fixed start \(a\), the interval sum grows strictly as \(b\) grows:

$S(a,b+1)=S(a,b)+(b+1)^2.$

Because \((b+1)^2>0\), once \(S(a,b)\ge 10^8\) for some end point \(b\), every larger end point will also fail. This monotonicity is the key invariant that makes the double loop efficient: the inner scan for a fixed start can stop immediately at the first overshoot.

Worked example

Take \(a=6\) and \(b=8\). Then

$S(6,8)=6^2+7^2+8^2=36+49+64=149,$

and \(149\) is palindromic. Using prefix sums gives the same value more systematically:

$P_8=\frac{8\cdot 9\cdot 17}{6}=204,\qquad P_5=\frac{5\cdot 6\cdot 11}{6}=55,$

so

$S(6,8)=P_8-P_5=204-55=149.$

If we extend the interval by one term, the next sum is

$S(6,9)=149+9^2=230,$

which illustrates the strict upward march of the right endpoint and why the break condition is correct.

Why uniqueness matters

The problem asks for the sum of palindromic numbers that admit such a representation, not for the sum over all representations. Therefore the mathematically correct accumulator is a set of values, not a running total inside the nested loops. Whenever a palindromic interval sum reappears from a different pair \((a,b)\), it should leave the final answer unchanged.

How the Code Works

Building the prefix table

The C++, Python, and Java implementations first compute the least integer whose square is not below the limit and allocate a prefix array up to that point. Each entry stores the cumulative total \(1^2+2^2+\cdots+i^2\). This transforms every later interval query into a single subtraction.

Scanning all admissible intervals

The implementation then iterates over every start \(a\) and every end \(b>a\). For each pair it evaluates \(P_b-P_{a-1}\). If that value reaches the limit, the inner loop stops immediately because all larger end points would only increase the sum. Otherwise the decimal expansion is tested for the palindrome property by comparing it with its reversal.

Deduplicating and finishing the total

Whenever an interval sum is palindromic, it is inserted into a set of discovered values. After the full scan, the program adds the elements of that set to produce the final answer. The three languages follow the same mathematical routine; one implementation also performs a small checkpoint on the smaller limit \(10^3\), where the correct total is \(4164\), before tackling the full \(10^8\) search.

Complexity Analysis

Let \(L\) be the limit and \(B=\lceil\sqrt{L}\rceil\). Building the prefix table costs \(O(B)\) time and \(O(B)\) memory.

The nested enumeration has worst-case size \(O(B^2)\), because both endpoints live on the square-root scale. Each palindrome test inspects \(O(\log L)\) digits, so the overall worst-case running time is \(O(B^2\log L)\). For this problem \(L=10^8\) and \(B=10^4\), which is small enough for a direct search, especially because the monotone break prunes the inner loops aggressively. Memory usage is \(O(B+U)\), where \(U\) is the number of distinct palindromic sums retained in the set.

Footnotes and References

1. Problem page: Project Euler 125
2. Palindrome: Wikipedia - Palindrome
3. Sum of squares / square pyramidal numbers: Wikipedia - Square pyramidal number
4. Prefix sums: Wikipedia - Prefix sum
5. Sets as a uniqueness structure: Wikipedia - Set (abstract data type)