Problem 962: Taxicab Numbers

Mathematical Analysis

Hardy—Ramanujan Number

The most famous taxicab number is $\operatorname{Ta}(2) = 1729$, the Hardy—Ramanujan number. The anecdote is well-known: G. H. Hardy visited Ramanujan in hospital and remarked that his cab number 1729 seemed dull. Ramanujan instantly replied it was the smallest number expressible as the sum of two cubes in two different ways:

Theorem. $\operatorname{Ta}(2) = 1729$ is the smallest positive integer with two distinct representations as a sum of two positive cubes.

Proof. Enumerate all sums $a^3 + b^3$ with $1 \le a < b$ and $a^3 + b^3 \le 1729$. The cube root of 1729 is about 12.0, so $b \le 12$. Checking all pairs, the only sums that coincide are $1^3 + 12^3 = 9^3 + 10^3 = 1729$. For all $n < 1729$, each sum $a^3 + b^3 = n$ has at most one representation. $\square$

The Third Taxicab Number

$\operatorname{Ta}(3) = 87539319$ was discovered by John Leech in 1957:

Verification:

• $167^3 = 4657463$, $436^3 = 82881856$, sum $= 87539319$. Correct.
• $228^3 = 11852352$, $423^3 = 75686967$, sum $= 87539319$. Correct.
• $255^3 = 16581375$, $414^3 = 70957944$, sum $= 87539319$. Correct.

Parametric Families

Ramanujan discovered the parametric identity:

However, taxicab numbers are defined as the smallest with $n$ representations, so parametric families alone don’t suffice.

Known Taxicab Numbers

Computing the Answer

Since $87541048 < 10^9 + 7$, the answer modulo $10^9 + 7$ is simply $87541048$.

Derivation

Algorithm for Taxicab Numbers

Use a hash map to find collisions among sums $a^3 + b^3$:

1. For $1 \le a \le b$ with $a^3 + b^3 \le \text{limit}$, compute $s = a^3 + b^3$.
2. Group all $(a, b)$ pairs by their sum $s$.
3. The smallest $s$ with $\ge n$ pairs is $\operatorname{Ta}(n)$.

Proof of Correctness

The enumeration is exhaustive within the search range. Each pair $(a, b)$ with $a \le b$ is considered exactly once.

Complexity Analysis

• $O(N^{2/3})$ pairs to enumerate where $N$ is the search limit.
• For $\operatorname{Ta}(3)$: $N \approx 10^8$, giving $\approx 444^2 / 2 \approx 10^5$ pairs.

Answer

/*
 * Problem 962: Taxicab Numbers
 *
 * Ta(2) = 1729, Ta(3) = 87539319
 * Answer = (1729 + 87539319) % (10^9 + 7) = 87541048
 *
 * Verification by exhaustive enumeration of a^3 + b^3.
 */

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

int main() {
    const long long MOD = 1e9 + 7;

    // Find Ta(2): smallest n = a^3 + b^3 with 2 representations
    map<long long, int> count2;
    long long ta2 = -1;
    for (int b = 1; b <= 13; b++) {
        for (int a = 1; a <= b; a++) {
            long long s = (long long)a*a*a + (long long)b*b*b;
            count2[s]++;
            if (count2[s] >= 2 && (ta2 == -1 || s < ta2)) {
                ta2 = s;
            }
        }
    }

    // Find Ta(3) = 87539319 (verify)
    map<long long, int> count3;
    long long ta3 = -1;
    int lim = 445;
    for (int b = 1; b <= lim; b++) {
        for (int a = 1; a <= b; a++) {
            long long s = (long long)a*a*a + (long long)b*b*b;
            if (s > 100000000) break;
            count3[s]++;
            if (count3[s] >= 3 && (ta3 == -1 || s < ta3)) {
                ta3 = s;
            }
        }
    }

    assert(ta2 == 1729);
    assert(ta3 == 87539319);

    long long ans = (ta2 + ta3) % MOD;
    cout << ans << endl;
    return 0;
}

"""
Problem 962: Taxicab Numbers

Ta(2) = 1729 (Hardy-Ramanujan number)
Ta(3) = 87539319 (Leech, 1957)

Answer: Ta(2) + Ta(3) mod (10^9 + 7) = 87541048

Verification by exhaustive enumeration of cube-sum representations.
"""

from collections import defaultdict

MOD = 10**9 + 7

def find_taxicab(target_reps: int, limit: int) -> tuple[int, dict]:
    """Find smallest number expressible as sum of two positive cubes
    in target_reps distinct ways. Search up to limit."""
    reps = defaultdict(list)
    b_max = int(limit ** (1/3)) + 1
    for b in range(1, b_max + 1):
        for a in range(1, b + 1):
            s = a**3 + b**3
            if s > limit:
                break
            reps[s].append((a, b))

    candidates = [(s, r) for s, r in reps.items() if len(r) >= target_reps]
    if not candidates:
        return -1, {}
    candidates.sort()
    return candidates[0][0], dict(candidates[:10])

# --- Compute answer ---
ta2, _ = find_taxicab(2, 2000)
ta3, _ = find_taxicab(3, 10**8)

assert ta2 == 1729
assert ta3 == 87539319

answer = (ta2 + ta3) % MOD
print(f"Ta(2) = {ta2}")
print(f"Ta(3) = {ta3}")
print(f"Ta(2) + Ta(3) = {ta2 + ta3}")
print(answer)