While reading The Algorithm Design Manual, I found a problem that seemed like a classic mathematical calculation, but had no solution in the wiki. After a decent amount of Googling, I found only two algorithms online: a O(n4) brute-force approach, and a O(n3) dynamic programming approach. For those reading the book after me, I'd like to offer my O(n2) solution.
I'll describe the problem and solution below, but if you're impatient, you can peek ahead to the code.
The Problem
The problem describes a Ramanujan number as a number that can be expressed as the sum of two distinct pairs of cubes. That is, a Ramanujan number r = a3 + b3 = c3 + d3, where a != b != c != d.
The goal is to design an algorithm that will generate all of the Ramanujan numbers where a, b, c, d < n.
Note that this is different from a similar problem you may see, which is to generate all Ramanujan numbers up to n. The problems can be solved in similar ways, but this other one essentially cuts the search space down to n1/3, since any a, b, c, or d must be less than the cube root of n.
Approach
My first thought was that we will want to calculate and store in an array all x3 for 0 < x < n. These are the numbers we're working with, and it will be easier to use them directly than to deal with x3 all the time.
I didn't see a way around checking nearly every pair of cubes. There are a few pairs we know can't be part of a Ramanujan number: the first two and last two cubes are obviously going to be smaller and greater, respectively, than any other pair. Also, the pair (13, 33) can't be used, since the next smallest pair is (23, 43), and 13 < 23, and 33 < 43. The same goes for the analogous pair at the top — clearly these have no equals. But trying to rule out other pairs seems to end up just comparing all of them anyway. I didn't end up removing the pairs discussed above, since it adds a lot of code for no noticeable gain.
Calculating every pair of n cubes takes O(n2) time, because there are (n(n – 1))/2 combinations of 2 elements from a set of size n. If we then summed each pair, we would know that any equal sums are Ramanujan numbers. With this approach, we don't actually have to worry about a, b, c, and d not being distinct due to an overlap in the pairs. It is clear that for any distinct a and b (which all of our pairs are), there exists no c where c != a and c != b, such that a3 + b3 = c3 + a3, or a3 + b3 = c3 + b3.
Implementation
Since n2 can become a formidable number, I decided that it would be best to calculate sums and see if we have any matches at the same time as we are generating the combinations of cube pairs. This saves us from having to travel across all ~n2/2 pairs more than once. I stored each pair and sum in a dictionary, where the sum is the key. As I generated pairs, I checked to see if there was already an entry for the key: if there was, we found a Ramanujan number! I would then add both the existing entry and the newly-generated pair to a second dictionary, which contained only confirmed Ramanujan numbers as keys, and an array of pairs as entries. I used an array because, however unlikely, it seems entirely possible that a Ramanujan number may also be the sum of three or more distinct pairs of cubes.
For heavy-duty computation, you can certainly improve the implementation given here. But since I am interested in this problem for algorithmic design, and not actually calculating lists of numbers, I made it easy to write and follow.
Improvements
It seems that O(n2) is the optimal time, as it is the upper limit on the number of possible solutions, and it doesn't look like you can disqualify a significant number of combinations by rule. If you can think of improvements to the algorithm, I would love to hear them!