Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$, $a,b,c,d$ are distinct positive integers. Find all taxicab number $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:

  1. 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)$

  2. 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.

share|improve this question
    
Hey! Thanks for the update :-) –  Aryabhata Jan 13 '11 at 21:50
add comment

3 Answers

up vote 18 down vote accepted

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.

share|improve this answer
1  
Just to point out a small detail - initialize the array A (of length 2n^3) so A[i] = 0 in constant time. Now: for all pairs 0 < a < b < n do: A[a^3 + b^3] = A[a^3 + b^3] + 1 and if A[a^3 + b^3] == 2 then print a^3 + b^3. –  Sam Nead Aug 19 '10 at 22:21
    
The small detail is that you've either got to print inside the loop or you have to understand the internals of the "fake" initialization in constant time. –  Sam Nead Aug 19 '10 at 22:23
2  
Nice, you have achieved the lower bound that doesn't exploit any number theoretical property. I didn't know arrays can be initialized in constant time. Definitely good to know. –  Chao Xu Aug 19 '10 at 22:43
    
+1: Interesting approach :-) –  Aryabhata Aug 20 '10 at 0:32
3  
Refs for the array trick: Nicer pictures research.swtch.com/2008/03/… And my super-brief account of how someone can go about figuring out the O(1) array thing rgrig.blogspot.com/2008/12/array-puzzle-solution.html Oh, and the paper citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.7319 –  rgrig Aug 20 '10 at 9:11
show 1 more comment

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.

share|improve this answer
    
Are there any asymptotics for the number of taxicab numbers? –  Chao Xu Sep 28 '12 at 8:35
    
@ChaoXu: Sorry, no idea. –  Aryabhata Sep 28 '12 at 10:26
add comment

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)$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.