Introduction

The equation a^3 + b^3 = c^3 + d^3 is a classic equal-sums-of-cubes problem. A brute-force search over all quadruples from 1 to 10000 is far too expensive, so the right algorithm is to compute sums of cubes for pairs and group matching sums together.

Why Brute Force Is Not Practical

If you try every possible quadruple directly, the search space is about 10000^4, which is not remotely realistic.

The key observation is that the equation can be rewritten as:

(a, b) and (c, d) produce the same value of a^3 + b^3

So instead of thinking in quadruples first, think in pairs first.

Group Pair Sums by Value

For each pair (a, b), compute:

sum = a^3 + b^3

Store every pair that produces the same sum. Once all pairs are processed, any bucket containing more than one pair generates valid quadruples.

This turns the core search from “find matching quadruples” into “find collisions in pair sums.”

A Straightforward Python Implementation

1from collections import defaultdict
2
3
4def find_quadruples(limit: int):
5    sums = defaultdict(list)
6
7    for a in range(1, limit + 1):
8        a3 = a ** 3
9        for b in range(a, limit + 1):
10            sums[a3 + b ** 3].append((a, b))
11
12    results = []
13    for value, pairs in sums.items():
14        if len(pairs) > 1:
15            for i in range(len(pairs)):
16                for j in range(i + 1, len(pairs)):
17                    (a, b) = pairs[i]
18                    (c, d) = pairs[j]
19                    results.append((a, b, c, d, value))
20
21    return results
22
23
24for quadruple in find_quadruples(100):
25    print(quadruple)

This version uses b starting at a to avoid duplicate symmetric pair orderings such as (2, 3) and (3, 2).

Why the Pair Ordering Restriction Helps

Because:

a^3 + b^3 = b^3 + a^3

there is no need to store both (a, b) and (b, a) if you are only interested in mathematical solutions rather than ordered duplicates.

Using for b in range(a, limit + 1) almost halves the pair count and makes the output cleaner.

A Famous Example

One well-known collision is:

1^3 + 12^3 = 9^3 + 10^3 = 1729

This is the famous Ramanujan taxicab number example. The algorithm above finds that kind of collision naturally because both pairs end up in the same bucket for 1729.

Complexity Tradeoff

The approach still requires O(n^2) pair generation, which is large for n = 10000, but it is vastly better than O(n^4).

The real challenge at 10000 is memory. The number of stored pairs is enormous, so a full in-memory solution may be too heavy depending on the environment.

In practice, for such a high limit, you may need one of these strategies:

• restrict output or search scope
• stream sorted pair sums from disk
• process the space in chunks
• use a language and memory layout suited for large-scale numeric work

The core algorithmic idea stays the same.

When You Want All Ordered Quadruples

If you truly want ordered quadruples, then after finding unordered matching pairs, you can expand permutations such as swapping a with b or c with d.

But many mathematical formulations treat (a, b) and (b, a) as the same pair, so clarify the requirement before multiplying the output size.

Common Pitfalls

A common mistake is attempting the direct four-loop brute force, which is infeasible at this scale.

Another pitfall is forgetting the symmetry and storing both (a, b) and (b, a) without a reason.

Developers also sometimes underestimate the memory cost of keeping every pair up to 10000 in a Python dictionary.

Finally, be explicit about whether equal pairs are allowed and whether output should be ordered or canonicalized.

Summary

• The efficient idea is to group pairs (a, b) by the value of a^3 + b^3.
• Matching pair sums produce valid quadruples.
• Restricting to a <= b avoids symmetric duplicates.
• The algorithm is O(n^2) in pair generation, which is much better than O(n^4).
• At very large limits such as 10000, memory becomes the main practical constraint.