What three cube numbers sum to 29? Obviously, 3^3 + 1^3 + 1^3 works. What about 42? Well, the first ever solution was only discovered in 2019! It is 80435758145817515^3 + (−80538738812075974)^3 + 12602123297335631^3. Finding the three cubes which sum to a given number is a famous problem in the field of Diophantine equations, with many new results discovered in the past decade.

The algorithm to find these using a computer makes use of many breakthroughs in mathematics and computer science. Naively, you might nest three loops to get O(n^3) time complexity, but for the above solution you’d need to search at least 10^51 combinations, which is more than the number of atoms on Earth.

Researchers in the field have optimised the algorithm mathematically to about O(B(log log B)^(1+o(1))), where B is the upper bound for min(|x|, |y|, |z|). This still required large amounts of computing power for the new solutions found recently. The last possible number under 100 to be solved was 42 in 2019, which was possible through crowdsourced compute power from people’s spare computers.

I implemented the algorithm in C, and although I didn’t find new solutions (my laptop isn’t quite powerful enough) I did re-discover many solutions, including 30 which was found in 1999.