Detailed mathematical approach

Problem Summary

We seek palindromic integers \(n\) that admit exactly four distinct representations of the form

$n=a^2+b^3,\qquad a,b \gt 1.$

The solver must identify the five smallest such palindromes and sum them, but the final Project Euler value is intentionally omitted here.

Mathematical Approach

For a fixed integer \(n\), define the representation count

$R(n)=\#\{(a,b)\in\mathbb{Z}_{\ge2}^2:\ n=a^2+b^3\}.$

We accept a candidate exactly when it is palindromic and \(R(n)=4\).

Counting Representations

For a chosen cube \(b^3\), the equation \(n=a^2+b^3\) is equivalent to

$a^2=n-b^3.$

Thus every admissible \(b\) produces at most one possible \(a\): we only have to test whether \(n-b^3\) is a perfect square. Since \(a\ge2\), the remainder must be at least \(4\), so the cube loop stops at \(b^3\le n-4\).

This explains the smallest admissible value as well:

$2^2+2^3=4+8=12.$

Therefore the implementation skips all palindromes below \(12\), and for every later candidate it performs exact integer-square-root checks.

Why Search Palindromes First?

A brute-force scan over all integers wastes almost all of its effort on numbers that are not palindromes. The code instead generates only palindromes. The number of \(d\)-digit palindromes is

$9\cdot 10^{\lceil d/2\rceil-1},$

whereas the number of all \(d\)-digit integers is \(9\cdot 10^{d-1}\). So the search space shrinks from size about \(10^d\) to size about \(10^{d/2}\), which is the main practical speedup.

Prefix Mirroring

If \(p\) is a \(k\)-digit prefix and \(\operatorname{rev}(p)\) denotes decimal digit reversal, then every palindrome is obtained by mirroring that prefix. The code uses

$\operatorname{pal}_{\mathrm{even}}(p)=p\cdot 10^k+\operatorname{rev}(p),$

$\operatorname{pal}_{\mathrm{odd}}(p)=p\cdot 10^{k-1}+\operatorname{rev}\!\left(\left\lfloor\frac{p}{10}\right\rfloor\right).$

The odd-length formula mirrors everything except the center digit, so no digit is duplicated. By iterating lengths increasingly and prefixes increasingly, palindromes are produced in strictly increasing numeric order. Hence the first five accepted values are automatically the five smallest answers.

Incremental Cube Cache

As the current palindrome grows, larger cubes become relevant. Recomputing \(2^3,3^3,4^3,\dots\) from scratch for each candidate would be wasteful, so the program stores all previously needed cubes in a list and extends that list only when necessary.

In other words, once \(b^3\) has been generated, it is reused for all future palindromes. This keeps the inner loop simple: iterate through cached cubes, stop when \(b^3+4>n\), and test whether the remainder is a square.

Worked Example: \(5229225\)

The C++ checkpoint uses the palindrome \(5229225\), because it has exactly four valid representations:

$5229225=2285^2+20^3=2223^2+66^3=1810^2+125^3=1197^2+156^3.$

So \(R(5229225)=4\), which makes it a valid hit.

Correctness Sketch

Exhaustiveness. Every positive decimal palindrome has a unique length and a unique left prefix. The mirroring formulas generate that palindrome exactly once.

Ordering. All \(d\)-digit palindromes are smaller than every \((d+1)\)-digit palindrome, and within one fixed length, increasing the prefix increases the palindrome. So the enumeration order is ascending.

Exact counting. For each admissible \(b\), the value \(n-b^3\) determines \(a\) uniquely if and only if it is a perfect square. Thus counting square remainders is exactly the same as counting pairs \((a,b)\).

Combining these facts shows that the algorithm returns precisely the first five palindromic integers with \(R(n)=4\).

How the Code Works

The helper make_palindrome builds candidates via prefix mirroring. ensure_cubes_up_to grows the cache of cubes just far enough for the current palindrome. Then count_representations loops over cached cubes and uses an integer square root to test whether the remainder is a square. The main loop increases the palindrome length until five hits have been collected. The Python and Java versions implement the same logic, and the C++ version additionally cross-checks the optimized search against brute force on a small limit.

Complexity Analysis

If \(N\) is the largest palindrome inspected, then the number of palindromic candidates up to \(N\) is \(\Theta(\sqrt{N})\), because a palindrome is determined by roughly half of its digits. For one candidate \(n\), representation counting tests cubes up to \(n^{1/3}\), so it costs \(O(n^{1/3})\) time with \(O(1)\) work per cube. Therefore the total search cost up to horizon \(N\) is bounded by

$O\!\left(\sqrt{N}\,N^{1/3}\right)=O(N^{5/6}).$

The memory usage is \(O(N^{1/3})\) for the cached cubes. This is much better than scanning all integers up to \(N\), which would already require \(\Theta(N)\) candidate checks before counting representations.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=348
2. Palindromic numbers: Wikipedia — Palindromic number
3. Perfect squares: Wikipedia — Square number
4. Integer square root: Wikipedia — Integer square root
5. Diophantine equations: Wikipedia — Diophantine equation