# 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:

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.

• Hey! Thanks for the update :-) Jan 13, 2011 at 21:50
• I posted a faster algorithm for this problem Feb 17, 2016 at 23:46

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.

• 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. Aug 19, 2010 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. Aug 19, 2010 at 22:23
• 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. Aug 19, 2010 at 22:43
• 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 Aug 20, 2010 at 9:11
• Very interesting trick. It's worth noting, though, that technically (!) this takes logarithmic time to access elements, not constant; the array index needs to be large enough to point to n elements, so at least lg n bits, and reading lg n bits takes logarithmic time. Sep 13, 2010 at 13:34

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.

• Are there any asymptotics for the number of taxicab numbers? Sep 28, 2012 at 8:35
• @ChaoXu: Sorry, no idea. Sep 28, 2012 at 10:26

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

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] 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. :)

• so this would be similar to sorting X+Y cs.smith.edu/~orourke/TOPP/P41.html Aug 13, 2014 at 8:58
• The complexity is O(n^2 log n) since you can have up to n values that can be the next smallest value (one from each row). This is of-course the worse-case (big-O) complexity, the average complexity might be smaller, although that is data dependant. Aug 26, 2015 at 9:46
• @gen-y-s That is clearly incorrect, since you can merge n sorted lists in n^2, so I could just do that (treating the columns as individual sorted lists, say) and then read through the sorted list in linear time. This will be (marginally) faster than that. So the whole algorithm is n^2 Aug 26, 2015 at 11:03
• @phil_20686 really? how do you merge n sorted lists in O(n^2) ? I think you got confused.... merging n sorted lists is O(m log n) where m is the total length of all lists (en.wikipedia.org/wiki/Merge_algorithm) Aug 26, 2015 at 11:47
• hahaha, this is basic stuff.... p..w..n Aug 26, 2015 at 13:02

There is a faster algorithm to check if a given integer is a sum (or difference) of two cubes $n=a^3+b^3$

I don´t know if this algorithm is already known (probably yes, but I can´t find it on books or internet). I discovered and use it to compute integers to $n < 10^18$

This process uses a single trick

$4(a^3+b^3)/(a+b) = (a+b)^2 + 3(a-b)^2$

We don´t know in advance what would be "a" and "b" and so what also would be "(a+b)", but we know that "(a+b)" should certainly divide $(a^3+b^3)$ , so if you have a fast primes factorizing routine, you can quickly compute each one of divisors of $(a^3+b^3)$ and then check if

$(4(a^3+b^3)/divisor - divisor^2)/3 = square$

When (and if) found a square, you have $divisor=(a+b)$ and $sqrt(square)=(a-b)$ , so you have a and b.

If not square found, the number is not sum of two cubes.

We know $divisor < (4(a^3+b^3)^(1/3)$ and this limit improves the task, because when you are assembling divisors of $(a^3+b^3)$ immediately discard those greater than limit.

Now some comparisons with other algorithms - for n = 10^18, by using brute force you should test all numbers below 10^6 to know the answer. On the other hand, to build all divisors of 10^18 you need primes until 10^9.

The max quantity of different primes you could fit into 10^9 is 10 $(2*3*5*7*11*13*17*19*23*29 = 5*10^9)$ so we have 2^10-1 different combinations of primes (which assemble the divisors) to check in worst case, many of them discarded because limit.

To compute prime factors I use a table with first 60.000.000 primes which works very well on this range.

Hi Tito, I think my poor notebook and FreeBasic language can´t manage these monster numbers.

I made this algorithm to try solve $a^3+b^3 = n*c^3$ (all integers), and it works very fast even in my notebook, but I can´t manage numbers greatert than 10^18 because 64 bits limitation of language.

I also have Ubasic program which have no limits for digits, but on the other hand it has no resources to manage tables with 60 million primes.

Take this example: I searched now all solucions for $a^3+b^3 = 1729*c^3$ with c<10^6 and program found these solutions in some 10 (ten) minuts.

$12^3 + 1^3 = 1729 * 1^3$ , $10^3 + 9^3 = 1729 * 1^3$ , $46^3 + -37^3 = 1729 * 3^3$ , $453^3 + -397^3 = 1729 * 26^3$ , $24580^3 + -24561^3 = 1729 * 271^3$ , $20760^3 + -3457^3 = 1729 * 1727^3$ , $25503^3 + -18503^3 = 1729 * 1810^3$ , $30151^3 + -1479^3 = 1729 * 2512^3$ , $2472830^3 + -1538423^3 = 1729 * 187953^3$ , $2879081^3 + 622072^3 = 1729 * 240681^3$ , $5328703^3 + -182620^3 = 1729 * 443967^3$

Miguel

• Miguel: Accdg to sequence A011541, Taxicab(7) is not known but is assumed to be $<2.5\times10^{28}$. How fast can your algorithm search up to this range? Feb 18, 2016 at 0:14
• I think can't manage these numbers, I added response in my post. Feb 18, 2016 at 2:15