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.