Project Euler Problem 348

Solution

Answer: 1004195061

Let a number $N$ be representable as

$$N = a^2 + b^3$$

with $a>1$ and $b>1$.

We seek the five smallest palindromic numbers that admit exactly four distinct representations of this form.

---

Mathematical analysis

We need to combine three ideas:

1. Generate palindromes efficiently.
2. Test whether a palindrome can be written as a square plus a cube.
3. Count representations exactly.

---

1. Why generate palindromes directly?

Checking every integer is wasteful because palindromes are sparse.

A palindrome is completely determined by its first half.

Examples:

• Even length:

$$123321$$

comes from mirroring $123$.

• Odd length:

$$12321$$

comes from mirroring all but the last digit of $123$.

Thus we can generate palindromes in increasing order very cheaply.

---

2. Counting representations

For a fixed palindrome $N$, we want all pairs

$$(a,b), \qquad a>1,; b>1$$

such that

$$a^2 + b^3 = N.$$

Rearrange:

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

So for every cube $b^3 < N$:

1. Compute

$$r = N - b^3.$$ 2. Check whether $r$ is a perfect square.

A fast perfect-square test is:

$$a = \lfloor \sqrt{r} \rfloor,$$

then verify

$$a^2 = r.$$

Each successful check gives one representation.

---

3. Complexity

Suppose $N$ is around $10^9$.

Then:

$$b^3 \le N \quad\Rightarrow\quad b \le N^{1/3} \approx 1000.$$

So each palindrome requires only about $1000$ cube checks — very manageable.

Since palindromes are sparse, this brute force becomes practical.

---

Python implementation

from math import isqrt

def generate_palindromes(limit):
    """
    Generate palindromes in increasing order up to 'limit'.
    """

    length = 1

    while True:
        # Number of digits used to build the first half
        start = 10 ** ((length - 1) // 2)
        end = 10 ** ((length + 1) // 2)

        for half in range(start, end):
            s = str(half)

            # Odd length palindrome
            if length % 2 == 1:
                p = int(s + s[-2::-1])

            # Even length palindrome
            else:
                p = int(s + s[::-1])

            if p > limit:
                return

            yield p

        length += 1

def count_representations(n):
    """
    Count representations of n as:
        n = a^2 + b^3
    with a > 1 and b > 1.
    """

    count = 0
    b = 2

    while b ** 3 < n - 4:
        cube = b ** 3
        remainder = n - cube

        a = isqrt(remainder)

        if a > 1 and a * a == remainder:
            count += 1

        b += 1

    return count

# Search for the first five palindromes
# having exactly four representations.

found = []

LIMIT = 2_000_000_000

for p in generate_palindromes(LIMIT):

    if count_representations(p) == 4:
        found.append(p)

        print("Found:", p)

        if len(found) == 5:
            break

answer = sum(found)

print("Sum =", answer)

---

Code walkthrough

generate_palindromes(limit)

This function constructs palindromes directly.

Example:

If half = 123

• odd-length:

"123" + "21" -> 12321

• even-length:

"123" + "321" -> 123321

This guarantees palindromes appear in increasing order.

---

count_representations(n)

For every integer $b \ge 2$:

1. Compute

$$b^3$$ 2. Compute

$$n - b^3$$ 3. Check whether the remainder is a perfect square.

The integer square root function isqrt() makes this exact and fast.

---

Verification with the example

For

$$5229225$$

the program finds exactly four representations:

$$2285^2 + 20^3$$

$$2223^2 + 66^3$$

$$1810^2 + 125^3$$

$$1197^2 + 156^3$$

matching the statement perfectly.

---

The five smallest qualifying palindromes

The computation finds:

$$5229225$$

$$37088073$$

$$56200265$$

$$108909801$$

$$796767697$$

Their sum is:

$$1004195061$$

The magnitude is reasonable: the fifth qualifying palindrome already lies near $8\times10^8$, so a total around $10^9$ is expected.

---

Answer: 1004195061