Find taxicab numbers in $O(n)$ time This is a final exam question in my algorithms class:
$k$ is a taxicab number if $k = a^3+b^3=c^3+d^3$, and $a,b,c,d$ are distinct positive integers. Find all taxicab numbers $k$ such that $a,b,c,d < n$ in $O(n)$ time.
I don't know if the problem had a typo or not, because $O(n^3)$ seems more reasonable. The best I can come up with is $O(n^2 \log n)$, and that's the best anyone I know can come up with. 
The $O(n^2 \log n)$ algorithm: 


*

*Try all possible $a^3+b^3=k$ pairs, for each $k$, store $(k,1)$ into a binary tree(indexed by $k$) if $(k,i)$ doesn't exist, if $(k,i)$ exists, replace $(k,i)$ with $(k,i+1)$

*Transverse the binary tree, output all $(k,i)$ where $i\geq 2$
Are there any faster methods? This should be the best possible method without using any number theoretical result because the program might output $O(n^2)$ taxicab numbers. 
Is $O(n)$ even possible? One have to prove there are only $O(n)$ taxicab numbers lesser than $2n^3$ in order to prove there exist a $O(n)$ algorithm.
Edit: The professor admit it was a typo, it should have been $O(n^3)$. I'm happy he made the typo, since the answer Tomer Vromen suggested is amazing.
 A: For $O(n^2)$ (randomized) time, you can also use a hashtable of size $\Theta(n^2)$. Looking up will be constant time because the number of taxicab numbers is $O(n^2)$.
A: I don't know about $O(n)$, but I can do it in $O(n^2)$. The main idea is to use initialization of an array in $O(1)$ (this is the best reference that I've found, which is weird since this seems like a very important concept). Then you iterate through all the possible $(a,\ b)$ pairs and do the same as step 1 in your proposed algorithm. Since $a^3+b^3 \leq 2n^3$, the array needs to be of size $2n^3$, but it's still initialized in $O(1)$. Accessing an array element is $O(1)$ like in a regular array.
A: I think you can do better, imagine the (a,b) pairs as forming a matrix filled in with a^3+b^3 in the upper right triangle. e.g. (for squares due to limited mental arithmetic)
2, 5, 10, 17, 26
-  8, 13, 20, 29
-  -, 18, 25, 34
-  -   -  32, 41
-  -   -   -  50

So it should be clear from this that it is actually not hard to generate the numbers almost in order. I start by computing the top left, and I go down columns to the end unless the top of the next column is larger. So an implementation would be something like:
(1) Work out all the elements in the top row and put them in the bottom row of [N][2] So we would have the first row
[1,1,1,1,1]
[2,5,10,17,26]

So i try to go "down" the first row, but its exhausted, so I put 2 in an int which stores my last value. and i replace it with a 0 to indicate that column is exhausted.
[0,1,1,1,1]
[0,5,10,17,26]
lastVal=2

So now I see that 5 is the smallest value, so I take 5 and I increment that column. as long as that is less than the head of the next column its all fine, so the first interesting case is 
[0,0,2,1,1]
[0,0,13,17,26]

So when i take 13 for my last value, i find that the next value is 18 which is larger than 17, so i must next take 17 and increment that column. And I keep moving along incrementing until the list is once again sorted left to right.
Since I am generating them in order, i find all pairs immediately (value=last value), and I never need to hold more than N values in memory. In practice this is probably very close to n^2 in time, as it will not often have to make more than one comparison per number since at the end of every step its sorted left to right. Working out its actual complexity is too hard for me though. :)
A: Apparently this is a solved problem and every rational solution to $x^3 + y^3 = z^3 + w^3$ is proportional to
$x = 1 − (p − 3q)(p^2 + 3q^2)$
$y = −1 + (p + 3q)(p^2 + 3q^2)$
$z = (p + 3q) − (p^2 + 3q^2)^2$
$w = −(p − 3q) + (p^2 + 3q^2)^2$
See: http://129.81.170.14/~erowland/papers/koyama.pdf, Page 2.
Also see: http://sites.google.com/site/tpiezas/010 (search for J. Binet).
So it seems like an O(n^2) algorithm might be possible. Perhaps using this more cleverly can give us an O(n) time algorithm.
Hope that helps. Please do update us with the solution given by your professor.
