Problem 348: Sum of a Square and a Cube

Detailed mathematical approach

Problem Summary

A decimal palindrome reads the same in both directions, as \(252\) does. For a positive integer \(n\), let \(R(n)\) count the pairs \((a,b)\) with \(a\gt1\), \(b\gt1\) and \(n=a^2+b^3\). We must find the five smallest palindromes with \(R(n)=4\) exactly and add them. The statement offers \(5229225\), with its four representations ^[1]

$$\begin{aligned}5229225&=2285^2+20^3\\&=2223^2+66^3\\&=1810^2+125^3\\&=1197^2+156^3.\end{aligned}$$

Both parts must exceed \(1\), so the smallest number of this shape is \(2^2+2^3=12\).

The whole solution in one sentence: run through the palindromes in increasing order, count for each the cubes that leave a perfect square behind, and keep those whose count is exactly four until five have been collected.

Mathematical Approach

Two facts carry the computation: a candidate costs about \(n^{1/3}\) steps to test, and only about \(\sqrt N\) palindromes lie below \(N\).

1. One cube fixes its square

If \(n=a^2+b^3\) then \(a\) is forced once \(b\) is known, since \(a^2=n-b^3\) and a positive integer has one positive square root. Two distinct pairs therefore never share a \(b\), and

$$R(n)=\#\bigl\{\,b\ge2:\ \sqrt{n-b^3}\in\mathbb Z_{\ge2}\,\bigr\}.$$

The requirement \(a\ge2\) means \(n-b^3\ge4\), so the useful cubes are those with \(2\le b\le(n-4)^{1/3}\). Counting \(R(n)\) therefore costs at most \(\lfloor(n-4)^{1/3}\rfloor-1\) square tests, which also bounds \(R(n)\).

Substituting \(x=-b\) and \(y=a\) turns this into \(y^2=x^3+n\), a Mordell curve, whose integer points Mordell proved finite in number; ^[9] here the bound \(b^3\le n-4\) makes that unnecessary. OEIS catalogues the numbers representable this way, but admits \(1^2\) and \(1^3\). ^[4]

2. A candidate worked out by hand

Take \(n=252\). Since \(b^3\le248\), only \(b=2,\dots,6\) can occur:

• \(252-2^3=244\), between \(15^2=225\) and \(16^2\): no.
• \(252-3^3=225=15^2\): a hit, \(a=15\).
• \(252-4^3=188\), between \(13^2\) and \(14^2\): no.
• \(252-5^3=127\), between \(11^2\) and \(12^2\): no.
• \(252-6^3=36=6^2\): a hit, \(a=6\).

So \(R(252)=2\), and \(252\) is the smallest palindrome with two representations; the smallest with one is \(33=5^2+2^3\), and three first appear at

$$\begin{aligned}37873&=179^2+18^3=165^2+22^3\\&=44^2+33^3.\end{aligned}$$

Four are far rarer, as Section 7 explains.

3. Deciding "perfect square" exactly

One accepted near-square would invent a representation. The integer square root of \(m\) is the greatest \(r\) with \(r^2\le m\), and \(m\) is a square precisely when \(r^2=m\). ^[5]

The C++ and Java code takes a floating-point root as a first guess, then raises \(r\) while \((r+1)^2\le m\) and lowers it while \(r^2\gt m\), which leaves \(r^2\le m\lt(r+1)^2\) whatever the guess was. C++ writes both comparisons as divisions so that no squaring can overflow; Java multiplies, which is safe for the remainders below \(10^9\) arising here. The correction is not cosmetic. Binary64 has \(53\) significand bits and its square root must be correctly rounded, ^[6] yet correct rounding can still carry the value across an integer: for \(q=2^{26}+1\) and \(m=q^2-1\), below \(2^{53}\), the rounded root is exactly \(q\), so truncation returns \(q\) although \(\lfloor\sqrt m\rfloor=q-1\). The loops repair it. Testing every \(m\lt10^9\), beyond the largest remainder arising here, found no mismatch, but that covers only this range. Python uses math.isqrt, the exact integer square root. ^[7]

4. Palindromes are thin on the ground

A palindrome of \(d\) digits is fixed by its first \(k=\lceil d/2\rceil\) digits, the rest being their mirror image, and the leading digit cannot be \(0\). So there are \(9\cdot10^{\lceil d/2\rceil-1}\) of them, confirmed by a direct count for \(d\le6\): \(9,9,90,90,900,900\). ^[2] Summing over \(d\le D\) gives the number below \(10^{D}\),

$$2\bigl(10^{D/2}-1\bigr),\qquad 11\cdot10^{(D-1)/2}-2,$$

for \(D\) even and odd respectively. For \(D=1,\dots,9\) these give

$$\begin{gathered}9,18,108,198,1098,\\1998,10998,19998,109998,\end{gathered}$$

matching the catalogued values. ^[3] Divided by \(\sqrt{10^{D}}\) these counts climb towards \(2\) along the even \(D\) — \(1.800\), \(1.980\), \(1.998\) at \(D=2,4,6\) — and towards \(11/\sqrt{10}\approx3.478\) along the odd ones. Any \(N\) is bracketed by two consecutive powers of ten, hence by two such counts, so the number of palindromes below \(N\) is \(\Theta(\sqrt N)\) — the square root of the \(\Theta(N)\) tests a scan of all integers would need.

5. Generating them in increasing order

Increasing order matters, because the first five accepted candidates are then the five smallest. Fix \(d\), put \(k=\lceil d/2\rceil\) and let the prefix \(p\) run over the \(k\)-digit numbers. Mirroring gives, for \(d=2k\) and \(d=2k-1\),

$$p\cdot10^{k}+\operatorname{rev}(p),$$

$$p\cdot10^{k-1}+\operatorname{rev}(\lfloor p/10\rfloor),$$

where \(\operatorname{rev}\) reverses the decimal digits and drops leading zeros. The odd case reverses \(p\) without its last digit, so the centre digit is written once: prefix \(12\) gives \(1221\), prefix \(123\) gives \(12321\), and prefix \(10\) gives \(1001\).

Both maps are bijections onto the \(d\)-digit palindromes, since the first \(k\) digits of the result are those of \(p\) and such a palindrome is fixed by them, and both increase, because numbers of equal length compare by their leading digits. As every \(d\)-digit number is below every \((d+1)\)-digit one, running \(d=1,2,3,\dots\) with \(p\) increasing inside each \(d\) yields every palindrome once, in increasing order — and it reproduced the sorted list of all \(1998\) palindromes below \(10^{6}\) exactly.

6. What the search costs

Up to a horizon \(N\) there are \(\Theta(\sqrt N)\) candidates at \(O(N^{1/3})\) square tests each, so the work is \(O(N^{5/6})\). Measured on the real enumeration, the \(19998\) palindromes below \(10^{8}\) take \(4937453\) square tests and the \(109998\) below \(10^{9}\) take \(76321225\), against \(N^{5/6}\) of \(4.64\cdot10^{6}\) and \(3.16\cdot10^{7}\).

The alternative enumerates pairs and tallies their palindromic sums in a hash table. Writing \(B_N=\lfloor(N-4)^{1/3}\rfloor\), the exact pair count is

$$T(N)=\sum_{b=2}^{B_N}\bigl(\lfloor\sqrt{N-b^3}\rfloor-1\bigr).$$

Substituting \(t=b/N^{1/3}\) turns \(T(N)/N^{5/6}\) into rectangles of width \(N^{-1/3}\) and height \(\sqrt{1-t^3}\), whose total approaches the area under that curve:

$$T(N)\sim cN^{5/6},$$

$$c=\int_{0}^{1}\sqrt{1-t^{3}}\,dt\approx0.84131.$$

For \(N=10^{8}\) the exact count \(3889368\) sits close to the prediction \(3905012\). Same growth, but this route stores every palindromic sum below \(N\), while the candidate scan keeps only a short list of cubes; C++ uses it on a small limit as a cross-check.

7. Why four representations are rare, and why they cluster

Consecutive squares differ by \(2a+1\), so squares near \(m\) thin out like \(1/(2\sqrt m)\). Treating the remainders as random integers of that density gives the heuristic sum

$$H(n)=\sum_{b=2}^{B_n}\frac{1}{2\sqrt{n-b^3}}\approx\frac{\lambda}{n^{1/6}},$$

$$\lambda=\frac12\int_{0}^{1}\frac{dt}{\sqrt{1-t^{3}}}\approx0.70109,$$

where \(B_n=\lfloor(n-4)^{1/3}\rfloor\) is the cube bound of Section 1. This guides averages only, not any single \(R(n)\), and it guides them well: averaged over \(n\le10^{7}\) it gives \(0.05732\) against a measured \(0.05681\), and at \(n=10^{9}\) it falls to \(0.02217\). The tail is another matter. Were a count \(X\) Poisson distributed with mean \(\mu\), the chance of exactly four events would be \(e^{-\mu}\mu^4/4!\); ^[11] with \(\mu\) the measured mean that predicts \(4.1\) integers below \(10^{7}\) with \(R=4\), and enumeration finds \(358\).

Congruences are part of the cause. Cubes modulo \(9\) take only the values \(0,1,8\) and squares only \(0,1,4,7\). ^[8] So for \(n\equiv0,1,8\pmod 9\) two of the three cube classes leave a square-compatible remainder, against one for the other six; and squares sit unevenly inside a class, since \(a^2\equiv0\pmod 9\) needs \(3\mid a\), making that class three times as rich as average and the classes \(1,4,7\) twice as rich. Together these give \(5/3\) of the naive estimate for \(n\equiv0,1,8\) and \(2/3\) for the rest, a ratio of \(5/2\); the measured group means over \(n\le10^{7}\) are \(0.09467\) and \(0.03789\), a ratio of \(2.499\). Applying the Poisson estimate within each class modulo \(504\) lifts the prediction from \(4.1\) to \(137\), narrowing the gap to \(358\) without closing it. No average can point at individual numbers, so the enumeration counts representations exactly.

8. Why the enumeration is complete

Section 5 produces every palindrome exactly once and in increasing order. The counters return \(\min(R(n),5)\) rather than \(R(n)\), stopping on a fifth representation; since the untested cubes could only raise the count, acceptance stays equivalent to \(R(n)=4\) — and no palindrome below \(10^{9}\) has more than four, so the cutoff never fires in range. Once five candidates are accepted, increasing order makes them the five smallest.

How the Code Works

In the C++ program, ^[10] parse_arguments recognises --skip-checkpoints and --target-count=k through parse_int_after_prefix. isqrt_u64 is the exact root of Section 3, seeding from std::sqrt on a long double and writing its corrections as (x+1) <= n/(x+1) and x > n/x. pow10_u64 and make_palindrome implement the mirroring of Section 5, appending the reversed digits of prefix/10 for odd lengths and of prefix for even ones.

ensure_cubes_up_to holds a shared vector of the cubes with \(b^3+4\le n\) and a cursor next_base; since solve visits palindromes in increasing order, each newly eligible cube is appended once, while the first ineligible one is recomputed on every later call until it qualifies. count_representations walks those cubes, breaks at cube + 4 > n, counts the remainders passing the square test, and stops once the count exceeds four. solve loops over the length, derives the prefix range from prefix_digits, skips palindromes below \(12\), and collects candidates counting exactly four until target_count are in hand.

run_checkpoints runs before solve unless disabled. It verifies that \(5229225\) has four representations, then compares two routines through \(200000\): brute_palindromes_with_exact_count, the pair enumeration of Section 6 tallying sums in an unordered_map and sorting the survivors, and fast_palindromes_with_exact_count, which scans the integers from \(12\) and counts only once is_palindrome succeeds.

Python mirrors prefixes with the slices s[-2::-1] and s[::-1] and counts through math.isqrt on unbounded integers; it also defines an is_palindrome helper that it never calls. C++ keeps candidates, cubes and the sum in u64, an alias for std::uint64_t, while Java holds those values as long inside ArrayList<Long> but counts and measures lengths with int, and its isqrt corrects a Math.sqrt guess by multiplication. Only C++ carries the checkpoints.

Complexity and Verification

The search performs \(O(N^{5/6})\) square tests up to a horizon \(N\), as Section 6 derives and its counts confirm. That is a time bound while arithmetic on these values counts as constant-time — true for the fixed-width integers of C++ and Java, not for Python's unbounded ones. Extending the cache through \(N\) stores \(\lfloor(N-4)^{1/3}\rfloor-1\) cubes, \(998\) for \(N=10^{9}\), and with a fixed target of five nothing else grows; only the cross-check needs more. The target is first reached among the nine-digit palindromes, where C++ and Java finish in well under a second and Python in a few seconds, all three printing the same value.

One caveat deserves saying plainly. A pair enumeration up to \(2\cdot10^{6}\) finds \(226\) palindromes with one representation, \(18\) with two, one with three and none with four, so at the limit \(200000\) the lists the checkpoint compares are both empty: it confirms that neither routine invents a hit, but never exercises a genuine four-representation palindrome. Setting exact_count to \(3\) in both comparison routines would exercise a nonempty result, since \(37873\) is the only palindrome below \(200000\) with exactly three representations; the --target-count option does not change the checkpoints.

Every figure above was recomputed from scratch for this article: the worked representations, the digit and cumulative palindrome counts, the generator against the sorted \(1998\) palindromes below \(10^{6}\), the pair enumeration against the per-candidate counting on every palindrome below \(2\cdot10^{6}\), the truncated double root over all \(10^{9}\) integers below \(10^{9}\) together with its failure at \((2^{26}+1)^2-1\), the operation and pair counts, and the means and ratios modulo \(9\). These are additional validation, not tests in the solution files.

Footnotes and References

The references supply the background facts used above; the cube-loop reduction, the palindrome counts and generator, the cost estimates and the congruence analysis are derived here.

1. Project Euler 348 — Sum of a Square and a Cube. The official statement asks for the sum of the five smallest palindromes expressible as a square plus a cube, both greater than 1, in exactly 4 different ways, and gives 5229225 as an example.
2. Wikipedia — Palindromic number. It counts palindromes length by length by the rule of product, 9 with two digits and 90 with three, and tabulates the counts below powers of ten; Section 4 derives the general formula.
3. OEIS A050250 — Number of nonzero palindromes less than 10ⁿ. Its terms 9, 18, 108, 198, 1098, 1998, 10998, 19998, 109998 are what Section 4's closed form gives for n = 1, …, 9.
4. OEIS A055394 — Numbers that are the sum of a positive square and a positive cube, with OEIS A054402 for those representable in more than one way. Both admit the parts 1² and 1³, which this problem excludes, so both are wider than the set R(n) counts.
5. Wikipedia — Integer square root. It defines the integer square root of y as the greatest m with m² ≤ y and describes the correction loops repairing an over- or underestimate, as the C++ and Java code does.
6. Wikipedia — IEEE 754. The square root is a required operation that must be correctly rounded from the infinitely precise result, and binary64 has a 53-bit significand; Section 3 uses both facts.
7. Python documentation — math.integer.isqrt. It returns the floor of the exact square root of a nonnegative integer, the greatest a with a² ≤ n, which the Python solution uses instead of a corrected floating-point root.
8. Wikipedia — Quadratic residue. Its table for prime-power moduli lists the squares modulo 9 as 0, 1, 4 and 7, four classes out of nine, the list Section 7 builds on.
9. Wikipedia — Mordell curve. A Mordell curve is an elliptic curve y² = x³ + n with n a fixed nonzero integer, and Mordell proved it has only finitely many integer points.
10. C++ — Euler348.cpp. The linked immutable revision contains isqrt_u64, make_palindrome, ensure_cubes_up_to, count_representations, solve and run_checkpoints, and is this article's implementation record.
11. NIST/SEMATECH e-Handbook — Poisson Distribution. It gives the probability of exactly x events as e^(−λ)λˣ/x! and lists λ as the mean; Section 7 uses the case x = 4 as an explicitly heuristic comparison.