Problem 348: Sum of a Square and a Cube

Mathematical Foundation

Theorem 1 (Representation Count). For a positive integer $n$, define

We seek palindromic $n$ with $r(n) = 4$.

Proof (well-definedness). For fixed $n$, the constraint $b^3 < n$ gives $b < n^{1/3}$, so $b$ ranges over finitely many values. For each $b$, at most one $a > 0$ satisfies $a^2 = n - b^3$ (namely $a = \sqrt{n - b^3}$ if this is a positive integer). Hence $r(n)$ is finite and computable. $\square$

Lemma 1 (Palindrome Structure). A $d$-digit palindrome is determined by its first $\lceil d/2 \rceil$ digits. The number of $d$-digit palindromes is $9 \times 10^{\lceil d/2 \rceil - 1}$ (the leading digit is nonzero).

Proof. A palindrome $n = \overline{a_1 a_2 \cdots a_d}$ satisfies $a_i = a_{d+1-i}$. The free digits are $a_1, \ldots, a_{\lceil d/2 \rceil}$ with $a_1 \in \{1,\ldots,9\}$ and $a_i \in \{0,\ldots,9\}$ for $i \ge 2$. $\square$

Lemma 2 (Search Bound). Since we need only 5 palindromes, and empirically the answer involves palindromes below $10^{9}$, we search palindromes up to $L = 10^{9}$. For each palindrome $n < L$:

• $b$ ranges from 1 to $\lfloor (L-1)^{1/3} \rfloor \approx 999$
• Checking whether $n - b^3$ is a perfect square costs $O(1)$ via integer square root

Proof. $b^3 < n < 10^9$ implies $b < 10^3$. Computing $\lfloor \sqrt{n - b^3} \rfloor$ and verifying its square equals $n - b^3$ is $O(1)$ arithmetic. $\square$

Editorial

We enumerate the admissible parameter range, discard candidates that violate the derived bounds or arithmetic constraints, and update the final set or total whenever a candidate passes the acceptance test.

Pseudocode

    results = []

    for d = 1, 2, 3, ...: // number of digits
        for each d-digit palindrome n (in increasing order):
            count = 0
            For b from 1 to floor(n^(1/3)):
                remainder = n - b^3
                If remainder <= 0 then stop this loop
                a = isqrt(remainder)
                If a * a == remainder and a >= 1 then
                    count += 1
                If count > target_count then stop this loop

            If count == target_count then
                results.append(n)
                If len(results) == num_needed then
                    Return sum(results)

Complexity Analysis

• Time: $O(P \cdot L^{1/3})$ where $P$ is the number of palindromes checked and $L$ is the search bound. With $P \approx 10^5$ palindromes below $10^9$ and $L^{1/3} \approx 10^3$, total is $O(10^8)$.
• Space: $O(1)$ beyond storing the results (palindromes are generated on the fly).

Answer

#include <bits/stdc++.h>
using namespace std;

bool is_palindrome(long long n) {
    string s = to_string(n);
    string r = s;
    reverse(r.begin(), r.end());
    return s == r;
}

int main() {
    // We search palindromes up to some limit
    const long long LIMIT = 1000000000LL; // 10^9 should be enough

    // For each palindrome, count ways to write it as a^2 + b^3
    // We'll generate palindromes and check each

    vector<long long> results;

    // Generate palindromes in order by iterating through possible values
    // Instead, iterate all numbers and check palindrome + count
    // More efficient: generate palindromes directly

    // Generate palindromes by building from half
    vector<long long> palindromes;

    // Single digit palindromes
    for (int d = 1; d <= 9; d++) palindromes.push_back(d);

    // Generate multi-digit palindromes
    for (int half_len = 1; half_len <= 5; half_len++) {
        long long start = 1;
        for (int i = 1; i < half_len; i++) start *= 10;
        long long end_ = start * 10;

        // Even length: half_len * 2
        for (long long h = start; h < end_; h++) {
            string s = to_string(h);
            string r = s;
            reverse(r.begin(), r.end());
            long long p = stoll(s + r);
            if (p < LIMIT) palindromes.push_back(p);
        }

        // Odd length: half_len + 1 + half_len - but we handle it as:
        // left half (half_len digits) + middle digit + reversed left half
        // Actually simpler: for odd length 2*half_len+1
        for (long long h = start; h < end_; h++) {
            string s = to_string(h);
            string r = s.substr(0, s.size() - 1);
            reverse(r.begin(), r.end());
            long long p = stoll(s + r);
            if (p < LIMIT) palindromes.push_back(p);
        }
    }

    sort(palindromes.begin(), palindromes.end());
    palindromes.erase(unique(palindromes.begin(), palindromes.end()), palindromes.end());

    for (long long pal : palindromes) {
        if (pal < 2) continue; // need a>=1, b>=1, so min is 1+1=2
        int count = 0;
        for (long long b = 1; b * b * b < pal; b++) {
            long long rem = pal - b * b * b;
            long long a = (long long)round(sqrt((double)rem));
            if (a >= 1 && a * a == rem) {
                count++;
            }
        }
        if (count == 4) {
            results.push_back(pal);
            if (results.size() == 5) break;
        }
    }

    long long sum = 0;
    for (long long v : results) sum += v;
    cout << sum << endl;

    return 0;
}

import math

def solve():
    LIMIT = 10**9

    def generate_palindromes(limit):
        """Generate all palindromes up to limit in sorted order."""
        pals = []
        # Single digit
        for d in range(1, 10):
            pals.append(d)

        # Multi-digit: generate by half
        for length in range(2, 11):
            half_len = (length + 1) // 2
            start = 10 ** (half_len - 1)
            end = 10 ** half_len
            for h in range(start, end):
                s = str(h)
                if length % 2 == 0:
                    p = int(s + s[::-1])
                else:
                    p = int(s + s[-2::-1])
                if p >= limit:
                    break
                pals.append(p)

        pals.sort()
        return pals

    palindromes = generate_palindromes(LIMIT)

    results = []
    for pal in palindromes:
        if pal < 2:
            continue
        count = 0
        b = 1
        while b ** 3 < pal:
            rem = pal - b ** 3
            a = int(math.isqrt(rem))
            if a >= 1 and a * a == rem:
                count += 1
            b += 1
        if count == 4:
            results.append(pal)
            if len(results) == 5:
                break

    print(sum(results))

if __name__ == "__main__":
    solve()