Journal of Integer Sequences, Vol. 2 (1999), Article 99.1.9 
The nth taxicab number is the least integer which can be expressed as a sum of two positive cubes in (at least) n distinct ways, up to order of summands. In [HW54], there is a constructive proof that for any n >= 1, there exist numbers which can be expressed in exactly n ways as a sum of two cubes (hereafter, we will call such numbers nway sums). This guarantees the existence of a least nway sum (that is, the nth taxicab number) for n >= 1, however, the construction given in [HW54] is of no help in finding the least nway sum.
The first taxicab number is trivially
The second taxicab number was first published by Frénicle de Bessy in 1657:
This particular number was immortalized by the following wellknown incident involving G. H. Hardy and Srinivasa Ramanujan:
I [G. H. Hardy] remember once going to see him [Ramanujan] when he was lying ill at Putney. I had ridden in taxicab No. 1729, and remarked that the number (7.13.19) seemed to be rather a dull one, and that I hoped it was not an unfavourable omen.
"No," he replied, "it is a very interesting number; it is the smallest number expressible as the sum of two [positive] cubes in two different ways." [R27, p. xxxv]
The appelation taxicab number, as well as the name HardyRamanujan number for the number 1729, arose from this incident.
Subsequent taxicab numbers were discovered by computer search. In 1957, Leech obtained
and in 1991 Rosenstiel, Dardis, and Rosenstiel [RDR91] found
This paper announces the author's discovery, in November 1997, of the fifth taxicab number
The taxicab numbers form sequence A011541 in [OEIS].
s = a_{1}^{3} + b_{1}^{3} = a_{2}^{3} + b_{2}^{3} = ... = a_{n}^{3} + b_{n}^{3}.
where a_{i} <= b_{i} for 1 < i < n. Without loss of generality, we assume a_{1} < a_{2} < ... < a_{n}.
A primitive nway sum is an nway sum for which the a_{i} and b_{i} taken together have no common factor. If an nway sum is nonprimitive, it can be divided by gcd(a_{1}, b_{1}, a_{2}, b_{2}, ..., a_{n}, b_{n})^{3}, reducing it to a primitive sum. For this reason, only primitive sums are considered interesting.
There are two techniques which are useful for constructing new primitive nway sums from known ones. I call these techniques combination and magnification.
The combination technique is used to combine two primitive nway sums into a primitive (n+1)way sum.
First, a preliminary definition:
Definition: Let n be a positive integer, and let c be the least positive integer such that there exists integer d with n = cd^{3}. c is called the cubefree part of n. The cubefree part of n is what is left after all nontrivial cubes have been divided out of n.
In order to apply the combination technique to two nway sums, both sums must have the same cubefree part. Let s and s´ be nway sums with cubefree part c. Then we have
s = cd^{3} = a_{1}^{3} + b_{1}^{3} = a_{2}^{3} + b_{2}^{3} = ... = a_{n}^{3} + b_{n}^{3}
s´ = cd´^{3} = a_{1}´^{3} + b_{1}´^{3} = a_{2}´^{3} + b_{2}´^{3} = ... = a_{n}´^{3} + b_{n}´^{3}.
These can be combined to give
s´´ = c(dd´)^{3}
= sd´^{3} = (a_{1}d´)^{3} + (b_{1}d´)^{3} = (a_{2}d´)^{3} + (b_{2}d´)^{3} = ... = (a_{n}d´)^{3} + (b_{n}d´)^{3}
= s´d^{3} = (a_{1}´d)^{3} + (b_{1}´d)^{3} = (a_{2}´d)^{3} + (b_{2}´d)^{3} = ... = (a_{n}´d)^{3} + (b_{n}´d)^{3}
This gives 2n representations of s´´ as a sum of two cubes. At least n of these representations must be distinct, since they are multiples of the n distinct representations of s. If exactly n of the representations are distinct, we can then divide out common factors to arrive at the same primitive nway sum for s and s´, whence s = s´, contrary to assumption. We must conclude that at least n + 1 of these representations are distinct, and that s´´ is at least an (n+1)way sum.
As an example, consider the two primitive 3way sums:
327763000 = 300^{3} + 670^{3} = 339^{3} + 661^{3} = 510^{3} + 580^{3}
26059452841 = 417^{3} + 2962^{3} = 1290^{3} + 2881^{3} = 2193^{3} + 2494^{3}
327763000 and 26059452841 each have the cubefree part 327763, which means that these sums can be combined. We obtain
26059452841000
= 327763000·43^{3} = (300·43)^{3} + (670·43)^{3} = (339·43)^{3} + (661·43)^{3} = (510·43)^{3} + (580·43)^{3}
= 26059452841·10^{3} = (417·10)^{3} + (2962·10)^{3} = (1290·10)^{3} + (2881·10)^{3} = (2193·10)^{3} + (2494·10)^{3}.
Out of six representations, four are distinct, and we obtain the 4way sum:
26059452841000 = 4170^{3} + 29620^{3} = 12900^{3} + 28810^{3} = 14577^{3} + 28423^{3} = 21930^{3} + 24940^{3}.
The magnification technique is used to obtain a primitive (n+1)way sum from a primitive nway sum.
The idea is simple. If we have a primitive nway sum
s = a_{1}^{3} + b_{1}^{3} = a_{2}^{3} + b_{2}^{3} = ... = a_{n}^{3} + b_{n}^{3}
we know that every cubic multiple of that sum will also be a (nonprimitive) nway sum:
sd^{3} = (a_{1}d)^{3} + (b_{1}d)^{3} = (a_{2}d)^{3} + (b_{2}d)^{3} = ... = (a_{n}d)^{3} + (b_{n}d)^{3}.
For some fortunate choice of multiple d^{3}, we might hope for the serendipitous appearance of a new representation:
sd^{3} = (a_{1}d)^{3} + (b_{1}d)^{3} = (a_{2}d)^{3} + (b_{2}d)^{3} = ... = (a_{n}d)^{3} + (b_{n}d)^{3} = a´^{3} + b´^{3}.
It turns out that often enough this hope is justified. For example, starting again with the 3way sum
327763000 = 300^{3} + 670^{3} = 339^{3} + 661^{3} = 510^{3} + 580^{3},
we multiply 327763000 successively by d^{3} = 1^{3}, 2^{3}, 3^{3}, etc, each time checking for a new representation. Finally, at d^{3} = 43^{3}, an unexpected(?) solution arises:
327763000·43^{3} = (300·43)^{3} + (670·43)^{3} = (339·43)^{3} + (661·43)^{3} = (510·43)^{3} + (580·43)^{3} = 4170^{3} + 29620^{3},
and we have found the 4way sum 26059452841000.
From a computational standpoint, exploiting the magnification technique to find nway sums is essentially a search procedure, whose feasibility relies heavily on the speedy detection of the extra representation, which is to say, the efficient complete solution of s = a^{3} + b^{3} for a and b given s. When implementing the magnification technique, I found that even a Bresenham search was not practical for the large s with which I was concerned. Fortunately, I was able to construct a more efficient algorithm to solve s = a^{3} + b^{3}, using some known favorable properties of s.
First, we note that s is of the form
s = (cube)·(nway sum)
We know the cube factor beforehand. The nway sum factor by definition has n distinct representations as a^{3} + b^{3} = (a + b)(a^{2}  ab + b^{2}), that is, n distinct representations as a product of two integers. From this observation we conclude that nway sums should be highly factorable (for example, the 3way sum 327763000 = 2^{3}·5^{3}·31·97·109). This means that s should be highly factorable, and in practice even large s can be factored quickly using trial division.
Given that s is highly factorable, the following is an efficient method for solving s = a^{3} + b^{3}:
It is not hard to show that this method generates all solutions to s = a^{3} + b^{3}.
The search for the fifth taxicab number arose from an attempt to extend sequence A003826 of [OEIS], the sequence of primitive 4way sums. Prior to my work, A003826 contained four entries, first published in [RDR91]. In order to extend this sequence, I wrote a computer program to search for nway sums. The program was written in the C programming language with 64bit arithmetic, and ran on a Sun Sparc 5 workstation.
The approach was straightforward: Generate a sequence S of all triples of the form (a, b, s = a^{3} + b^{3}) with a <= b, sorted on s, and detect and record runs of contiguous triples in S having equal s values. A run of n contiguous triples (a_{1}, b_{1}, s), (a_{2}, b_{2}, s), ..., (a_{n}, b_{n}, s) in S indicates that s is the nway sum
s = a_{1}^{3} + b_{1}^{3} = a_{2}^{3} + b_{2}^{3} = ... = a_{n}^{3} + b_{n}^{3}.
The run detection part is relatively easy, so the problem really devolves to the efficient generation of S. My algorithm was:
The run detector, for its part, detects and prints runs of n >= 3 contiguous triples with equal s values passed to it, which correspond to nway sums. The run detector need store no more than five triples at any time.
The only technical concern with this algorithm is that s might overflow in step 4. However, I determined beforehand that I would manually interrupt the program long before this could happen, which is also why there is no termination condition on the main loop.
I wrote several versions of this program. In the first, Q was implemented as a linked list. This program verified Leech's 1957 value for Ta(3) in less than a second. After running a month, it also verified the four least primitive 4way sums given in [RDR91], but was unable to find any new 4way sums.
Some time later, I applied the combination technique discussed in section 2 to the nway sums that had been computed by this first version of this program. This led me to discover the primitive 5way sum
Since Ta(5) <= t < 2^{64}, this discovery showed that Ta(5) could in principle be found using the same basic 64bit algorithm with which I had attacked A003826.
However, a quick estimate convinced me that verifying Ta(5) = t using the algorithm as it then stood would take several years. This prompted me to make several improvements to the algorithm. Most notably, Q was reimplemented as a heap, and a and b replaced by pointers into an array of precomputed cubes. These and other optimizations speeded up the program considerably, reducing a monthlong computation via the first version to less than one day. I estimated that Ta(5) = t could now be verified in approximately 8 months.
I began running the new program in earnest in October 1997. After I had run the program for about a month, I applied the magnification technique described in section 2 to its results. This led to the discovery of the yet smaller 5way sum 48988659276962496. On November 17, the program verified that this 5way sum was indeed Ta(5).
I later found that many of the basic search techniques I used to find Ta(5) had been used earlier by Bernstein on a variety of similar Diophantine problems. [B98] details Bernstein's techniques and discoveries. Though Bernstein did eventually apply his methods to sums of cubes, his independent discovery of Ta(5) = 48988659276962496 came a few months after mine.
The main product of my search for the Ta(5) was a exhaustive list of all 3, 4, and 5way sums of two cubes less than 5·10^{16} (2way sums were too numerous to record). The following table summarizes the counts of various types of nway sums found in the search:
Type of sum  n = 3  n = 4  n = 5 

All No constraints 
16159  143  1 
Primitive gcd(a_{1}, b_{1}, a_{2}, b_{2}, ..., a_{n}, b_{n}) = 1 
1630  35  1 
Coprime Pair gcd(a_{i}, b_{i}) = 1 for some i 
892  9  1 
All Pairs Coprime gcd(a_{i}, b_{i}) = 1 for all i 
81  0  0 
Prime Occurrence a_{i} or b_{i} prime for some i 
419  5  1 
Prime Pair a_{i}, b_{i} both prime for some i 
27  1  1 
In the following tables, primes are in red, and nonprime members of a coprime pair are in green.
The search program found the 1630 least primitive 3way sums of two cubes, too many to include in this article. Instead, I have composed several small tables of selected 3way sums.
81 3way sums of two cubes in which all pairs are coprime were found. Table 2 list the first 30 of these. Sums with all pairs coprime are hard to find, as they cannot be generated using the combination or magnification techniques described in Section 2, and their discovery lends some credence to the search algorithm. The s column of this table forms sequence A023050 of [OEIS].
#  s  a_{1}  b_{1}  a_{2}  b_{2}  a_{3}  b_{3} 

1  15170835645  517  2468  709  2456  1733  2152 
2  208438080643  1782  5875  3768  5371  4174  5139 
3  320465258659  1986  6787  2395  6744  5230  5619 
4  1658465000647  3488  11735  5231  11486  7127  10904 
5  3290217425101  4044  14773  4917  14692  8622  13837 
6  3938530307257  3057  15754  5289  15592  10732  13929 
7  7169838686017  6140  19073  8585  18698  9929  18362 
8  13112542594333  198  23581  2269  23574  11602  22605 
9  24641518275703  3687  29080  4575  29062  15039  27694 
10  36592635038993  10457  32850  15326  32073  22193  29496 
11  36848138663889  6518  33193  25342  27401  25625  27154 
12  41332017729268  157  34575  19273  32451  20679  31909 
13  74051580874005  5758  41957  17354  40981  25997  38368 
14  185496306251347  19906  56211  25212  55339  44691  45826 
15  198659972280259  14523  58048  30819  55330  38482  52131 
16  257103717556959  18094  63095  29728  61343  32126  60727 
17  263279186850871  29824  61863  36583  59844  49039  52578 
18  265244512323889  32337  61396  41488  57873  43900  56529 
19  322599256181839  22054  67815  26671  67212  38679  64210 
20  347866760139759  27215  68944  38300  66319  46286  62887 
21  351255019778299  14626  70347  17571  70192  51003  60238 
22  412229923045759  23487  73636  48319  66900  49863  66058 
23  437031592888969  16473  75628  21438  75313  48192  68761 
24  632989859046103  5262  85855  43335  82012  60354  74479 
25  703370246202351  5903  88924  30487  87722  59279  79108 
26  710103031199289  6505  89204  16082  89041  67297  74006 
27  782243102336787  14083  92030  50627  86734  57451  83996 
28  784136775183571  6564  92203  52995  85966  67443  78154 
29  1135806966295127  32852  103239  53511  99416  82695  82928 
30  1318372504623603  6616  109643  38963  107986  71530  98387 
27 3way sums of two cubes were found in which a prime pair occurs. Table 3 lists them all. Immediately it appears that a 3way sum with a prime pair will not admit another coprime pair. I am hesitant to conjecture this, though, since the analogous assertion for 2way sums is not true (e.g, 6058655748 = 61^{3} + 1823^{3} = 1049^{3} + 1699^{3} [K99] and 6507811154 = 31^{3} + 1867^{3} = 397^{3} + 1861^{3} [H99]).
#  s  a_{1}  b_{1}  a_{2}  b_{2}  a_{3}  b_{3} 

1  3623721192  348  1530  761  1471  1098  1320 
2  1097813860416  2862  10242  5939  9613  6372  9432 
3  2112174838440  1304  12826  2689  12791  4762  12608 
4  2210606903232  3100  12968  7727  12049  8968  11420 
5  3031368604992  3449  14407  8232  13524  10976  11956 
6  5422497850224  2574  17550  8406  16902  11443  15773 
7  8260081705512  2826  20196  5171  20101  11184  19002 
8  21661703776512  396  27876  16164  25932  19597  24179 
9  65129243036312  7408  40150  24169  37087  27880  35158 
10  189471941528112  8433  57375  16931  56941  35934  52302 
11  315078833433728  15790  67762  32083  65581  40204  63004 
12  633976914708592  7247  85889  7646  85886  39434  83042 
13  743035439587194  39451  88007  54283  83543  70965  72789 
14  1522143500400432  6186  115026  10711  115001  82322  98794 
15  2327887074691584  10337  132511  79344  122280  92094  115650 
16  3945585301003080  23  158017  73842  152448  118306  131804 
17  7074720483285672  19997  191899  52938  190620  63792  189594 
18  11563415577133056  71153  223759  83040  222336  138336  207360 
19  11889715109702976  77912  225172  100417  221567  171924  189528 
20  12595634712801000  10337  232663  14760  232650  36090  232380 
21  13725610143231168  57149  238339  82848  236076  86568  235596 
22  17162266133727288  35831  257713  97392  253230  159966  235548 
23  18293741864569080  101544  258366  154248  244542  203309  214651 
24  27716185298529000  86767  300233  198705  270855  234000  246090 
25  34481992947063480  72846  324264  190913  301927  217246  289364 
26  36149194839121000  73160  329450  99371  327629  175850  313160 
27  47607145051205376  42501  362235  156817  352367  185876  345340 
Table 4 gives the two sums discovered involving three primes:
#  s  a_{1}  b_{1}  a_{2}  b_{2}  a_{3}  b_{3} 

1  4895818255862163  58243  167486  86048  162091  115499  149704 
2  40778727507646891  52742  343787  138464  336563  255650  288731 
35 primitive 4way sums were found. This corroborates and greatly extends the list of four originally included in [RDR91]. The s column of Table 5 forms sequence A003826 of [OEIS]. As can be seen, only nine of the 4way sums (nos. 6, 7, 17, 19, 22, 25, 27, 30, and 35) involve a coprime pair, only five (nos. 7, 17, 22, 25, 30) include a prime, and just one (no. 25) involves a prime pair. Note also that no. 25 bolsters the theory that prime pairs in 3way sums do not admit other coprime pairs.
#  s  a_{1}  b_{1}  a_{2}  b_{2}  a_{3}  b_{3}  a_{4}  b_{4} 

1  6963472309248  2421  19083  5436  18948  10200  18072  13322  16630 
2  12625136269928  4275  23237  7068  23066  10362  22580  12939  21869 
3  21131226514944  1539  27645  8664  27360  11772  26916  17176  25232 
4  26059452841000  4170  29620  12900  28810  14577  28423  21930  24940 
5  74213505639000  5895  41985  20392  40358  20880  40230  32790  33900 
6  95773976104625  22020  43985  27866  42009  30918  40457  35660  36945 
7  159380205560856  4617  54207  8436  54150  31686  50340  34499  49093 
8  174396242861568  4041  55863  31160  52432  36684  50004  43200  45432 
9  300656502205416  10500  66906  19082  66472  30156  64890  42885  60531 
10  376890885439488  11184  72144  15560  71992  27411  70893  39296  68128 
11  521932420691227  427  80514  32539  78702  46228  75075  57603  69160 
12  573880096718136  7713  83079  16644  82878  40204  79838  48222  77292 
13  809541767245176  30359  92113  41976  90270  55548  86094  65310  80976 
14  926591497348608  5427  97485  30552  96480  60568  88976  76950  77802 
15  1002383007176376  2233  100079  18270  99876  50832  95502  70238  86884 
16  1698430189248000  25058  118942  27075  118845  50160  116280  55936  115064 
17  2983266899506341  27197  143632  50256  141885  68157  138672  98853  126354 
18  3281860456534296  44092  147302  85407  138537  100548  131334  104419  128933 
19  3924747381450168  46755  156357  57024  155214  108629  138259  115848  133326 
20  3989728990001664  8829  158595  13968  158568  49704  156960  98536  144752 
21  4011064622136936  21980  158746  56371  156485  85498  150164  103757  142507 
22  4145402010642984  55560  158394  69690  156144  89546  150772  102091  145517 
23  5342005020171456  25200  174636  36652  174272  133011  144045  137004  140448 
24  10546690302075375  1935  219300  53140  218255  92751  213624  140567  198058 
25  10998043552638016  21587  222317  48650  221606  95480  216356  130232  206372 
26  13334625130088808  5291  237133  43290  236652  68724  235194  166426  205868 
27  13796337654911448  19475  239797  50838  239076  164422  210680  186864  193734 
28  14923915104314944  27588  246088  84664  242820  107664  239140  158707  221901 
29  17690196319967808  70148  258856  73359  258609  95940  256152  144666  244758 
30  18170126765973000  16123  262877  77925  260595  95040  258690  193080  222210 
31  18307821317457672  81396  260946  89832  260034  167599  238697  197442  219744 
32  31943251595185749  54720  316749  131124  309645  204725  285874  243390  259749 
33  40842205643302336  35964  344248  116296  339900  189921  323935  255004  289488 
34  41799396718910376  120876  342090  150376  337370  176544  331098  206703  320649 
35  43819222861788696  132598  346184  155591  342145  181032  335862  202470  328716 
The only 5way sum discovered directly by the search was, of course
here colored to indicate primality. Surprisingly, this 5way sum includes a prime pair, again confirming that a prime pair in a 3way sum admits no other coprime pair.
On the lighter side, a single primitive 3way sum was found containing only even digits, and one containing only odd digits:
24248680282008000
= 78300^{3} + 287520^{3} = 208059^{3} + 247941^{3} = 227520^{3} + 231900^{3} 
9539173995131151
= 7308^{3} + 212079^{3} = 129367^{3} + 194642^{3} = 160534^{3} + 175463^{3} 
By combining results of the search as described in Section 2, it was possible to generate several additional primitive sums beyond the search range. For example, the following are some 5way sums and a 6way sum:
490593422681271000

6355491080314102272

27365551142421413376
 
1199962860219870469632

111549833098123426841016

8230545258248091551205888
= 11239317^{3} + 201891435^{3} = 17781264^{3} + 201857064^{3} = 63273192^{3} + 199810080^{3} = 85970916^{3} + 196567548^{3} = 125436328^{3} + 184269296^{3} = 159363450^{3} + 161127942^{3} 
These sums were known to me prior to my discovery of Ta(5), and are very small compared to what can be obtained by the methods described in [HW54]. 8230545258248091551205888 is currently the least known 6way sum.
[B98] D. J. Bernstein, Enumerating solutions to p(a) + q(b) = r(c) + s(d), Mathematics of Computation, to appear.
[HW54] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 3rd ed., Oxford University Press, London & NY, 1954, Thm. 412.
[H99] F. Helenius, personal communication, April 1999.
[K99] M. Kleber, personal communication, April 1999.
[R27] S. Ramanujan, Collected Papers, ed. G. H. Hardy, P. V. Seshu Aiyar and B. M. Wilson, Cambridge Univ. Press, 1927; reprinted, Chelsea, NY, 1962.
[RDR91] E. Rosenstiel, J. A. Dardis & C. R. Rosenstiel, The four least solutions in distinct positive integers of the Diophantine equation s = x^{3} + y^{3} = z^{3} + w^{3} = u^{3} + v^{3} = m^{3} + n^{3}, Bull. Inst. Math. Appl., 27(1991) 155157; MR 92i:11134.
[OEIS] N. J. A Sloane, Online Encyclopedia of Integer Sequences, http://oeis.org.
(Concerned with sequences A011541 , A023050 , A003826 .)
Received April 7, 1999; revised version received Oct. 15, 1999. Published in Journal of Integer Sequences Oct. 17, 1999.