Problem 348: Sum of a Square and a Cube

Project Euler Problem 348 Solution

EulerSolve provides an optimized solution for Project Euler Problem 348, Sum of a Square and a Cube, with C++, Python, Java, and a step-by-step mathematical explanation.

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}$....

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

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

Problem 348 source code

C++

#include <algorithm>
#include <cmath>
#include <cstdint>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

namespace {

using u64 = std::uint64_t;

struct Options {
    int target_count = 5;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }
    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--target-count=", options.target_count)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.target_count >= 1;
}

u64 isqrt_u64(const u64 n) {
    u64 x = static_cast<u64>(std::sqrt(static_cast<long double>(n)));
    while ((x + 1ULL) <= n / (x + 1ULL)) {
        ++x;
    }
    while (x > 0ULL && x > n / x) {
        --x;
    }
    return x;
}

bool is_palindrome(u64 value) {
    u64 reversed = 0ULL;
    u64 x = value;
    while (x > 0ULL) {
        reversed = reversed * 10ULL + (x % 10ULL);
        x /= 10ULL;
    }
    return reversed == value;
}

u64 pow10_u64(int exp) {
    u64 value = 1ULL;
    for (int i = 0; i < exp; ++i) {
        value *= 10ULL;
    }
    return value;
}

u64 make_palindrome(const u64 prefix, const bool odd_length) {
    u64 tail = odd_length ? prefix / 10ULL : prefix;
    u64 palindrome = prefix;
    while (tail > 0ULL) {
        palindrome = palindrome * 10ULL + (tail % 10ULL);
        tail /= 10ULL;
    }
    return palindrome;
}

void ensure_cubes_up_to(const u64 n, std::vector<u64>& cubes, u64& next_base) {
    while (true) {
        const u64 cube = next_base * next_base * next_base;
        if (cube + 4ULL > n) {
            break;
        }
        cubes.push_back(cube);
        ++next_base;
    }
}

int count_representations(const u64 n, const std::vector<u64>& cubes) {
    int count = 0;
    for (const u64 cube : cubes) {
        if (cube + 4ULL > n) {
            break;
        }
        const u64 remaining = n - cube;
        const u64 root = isqrt_u64(remaining);
        if (root >= 2ULL && root * root == remaining) {
            ++count;
            if (count > 4) {
                break;
            }
        }
    }
    return count;
}

std::vector<u64> brute_palindromes_with_exact_count(const u64 limit, const int exact_count) {
    std::unordered_map<u64, int> counts;
    for (u64 a = 2ULL; a * a <= limit; ++a) {
        const u64 square = a * a;
        for (u64 b = 2ULL;; ++b) {
            const u64 cube = b * b * b;
            if (square + cube > limit) {
                break;
            }
            const u64 value = square + cube;
            if (is_palindrome(value)) {
                ++counts[value];
            }
        }
    }
    std::vector<u64> result;
    for (const auto& row : counts) {
        if (row.second == exact_count) {
            result.push_back(row.first);
        }
    }
    std::sort(result.begin(), result.end());
    return result;
}

std::vector<u64> fast_palindromes_with_exact_count(const u64 limit, const int exact_count) {
    std::vector<u64> cubes;
    u64 next_base = 2ULL;
    ensure_cubes_up_to(limit, cubes, next_base);

    std::vector<u64> result;
    for (u64 value = 12ULL; value <= limit; ++value) {
        if (!is_palindrome(value)) {
            continue;
        }
        if (count_representations(value, cubes) == exact_count) {
            result.push_back(value);
        }
    }
    return result;
}

u64 solve(const int target_count) {
    std::vector<u64> cubes;
    u64 next_base = 2ULL;
    std::vector<u64> found;

    for (int length = 1; static_cast<int>(found.size()) < target_count; ++length) {
        const bool odd_length = (length % 2) == 1;
        const int prefix_digits = (length + 1) / 2;
        const u64 begin = (length == 1) ? 1ULL : pow10_u64(prefix_digits - 1);
        const u64 end = pow10_u64(prefix_digits) - 1ULL;

        for (u64 prefix = begin; prefix <= end; ++prefix) {
            const u64 palindrome = make_palindrome(prefix, odd_length);
            if (palindrome < 12ULL) {
                continue;
            }
            ensure_cubes_up_to(palindrome, cubes, next_base);
            if (count_representations(palindrome, cubes) == 4) {
                found.push_back(palindrome);
                if (static_cast<int>(found.size()) == target_count) {
                    break;
                }
            }
        }
    }

    u64 sum = 0ULL;
    for (const u64 v : found) {
        sum += v;
    }
    return sum;
}

bool run_checkpoints() {
    std::vector<u64> cubes;
    u64 next_base = 2ULL;
    ensure_cubes_up_to(5'229'225ULL, cubes, next_base);
    if (count_representations(5'229'225ULL, cubes) != 4) {
        std::cerr << "Checkpoint failed for statement palindrome 5229225" << '\n';
        return false;
    }

    const u64 small_limit = 200'000ULL;
    const std::vector<u64> brute = brute_palindromes_with_exact_count(small_limit, 4);
    const std::vector<u64> fast = fast_palindromes_with_exact_count(small_limit, 4);
    if (brute != fast) {
        std::cerr << "Checkpoint failed for brute-force cross-check at limit=200000" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }
    std::cout << solve(options.target_count) << '\n';
    return 0;
}

Python

import math

def solve():
    target_count = 5

    def isqrt(n):
        return math.isqrt(n)

    def is_palindrome(v):
        s = str(v)
        return s == s[::-1]

    def make_palindrome(prefix, odd_length):
        s = str(prefix)
        if odd_length:
            return int(s + s[-2::-1])
        else:
            return int(s + s[::-1])

    cubes = []
    next_base = [2]

    def ensure_cubes(n):
        while True:
            cube = next_base[0] ** 3
            if cube + 4 > n:
                break
            cubes.append(cube)
            next_base[0] += 1

    def count_reps(n):
        count = 0
        for cube in cubes:
            if cube + 4 > n:
                break
            remaining = n - cube
            root = isqrt(remaining)
            if root >= 2 and root * root == remaining:
                count += 1
                if count > 4:
                    break
        return count

    found = []
    length = 1
    while len(found) < target_count:
        odd_length = (length % 2) == 1
        prefix_digits = (length + 1) // 2
        begin = 1 if length == 1 else 10 ** (prefix_digits - 1)
        end = 10 ** prefix_digits - 1

        for prefix in range(begin, end + 1):
            palindrome = make_palindrome(prefix, odd_length)
            if palindrome < 12:
                continue
            ensure_cubes(palindrome)
            if count_reps(palindrome) == 4:
                found.append(palindrome)
                if len(found) == target_count:
                    break
        length += 1

    return str(sum(found))

if __name__ == '__main__':
    print(solve())

Java

import java.util.*;

public class Euler348 {

    static long isqrt(long n) {
        long x = (long) Math.sqrt(n);
        while ((x + 1) * (x + 1) <= n && (x + 1) > 0)
            x++;
        while (x * x > n)
            x--;
        return x;
    }

    static long pow10(int exp) {
        long val = 1;
        for (int i = 0; i < exp; i++)
            val *= 10;
        return val;
    }

    static long makePalindrome(long prefix, boolean oddLength) {
        long tail = oddLength ? prefix / 10 : prefix;
        long palindrome = prefix;
        while (tail > 0) {
            palindrome = palindrome * 10 + (tail % 10);
            tail /= 10;
        }
        return palindrome;
    }

    static void ensureCubesUpTo(long n, List<Long> cubes, long[] nextBase) {
        while (true) {
            long cube = nextBase[0] * nextBase[0] * nextBase[0];
            if (cube + 4 > n)
                break;
            cubes.add(cube);
            nextBase[0]++;
        }
    }

    static int countRepresentations(long n, List<Long> cubes) {
        int count = 0;
        for (long cube : cubes) {
            if (cube + 4 > n)
                break;
            long remaining = n - cube;
            long root = isqrt(remaining);
            if (root >= 2 && root * root == remaining) {
                count++;
                if (count > 4)
                    break;
            }
        }
        return count;
    }

    public static String solve() {
        int targetCount = 5;
        List<Long> cubes = new ArrayList<>();
        long[] nextBase = { 2L };
        List<Long> found = new ArrayList<>();

        for (int length = 1; found.size() < targetCount; length++) {
            boolean oddLength = (length % 2) == 1;
            int prefixDigits = (length + 1) / 2;
            long begin = (length == 1) ? 1L : pow10(prefixDigits - 1);
            long end = pow10(prefixDigits) - 1L;

            for (long prefix = begin; prefix <= end; prefix++) {
                long palindrome = makePalindrome(prefix, oddLength);
                if (palindrome < 12L)
                    continue;
                ensureCubesUpTo(palindrome, cubes, nextBase);
                if (countRepresentations(palindrome, cubes) == 4) {
                    found.add(palindrome);
                    if (found.size() == targetCount)
                        break;
                }
            }
        }

        long sum = 0;
        for (long v : found)
            sum += v;
        return String.valueOf(sum);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}