Journal of Integer Sequences, Vol. 2 (1999), Article 99.1.9

The Fifth Taxicab Number is 48988659276962496

David W. Wilson
263 E. Ricker Road
Loudon, NH 03301
Email address: wilson@ctron.com

Abstract: The nth taxicab number is the least number which can be expressed as a sum of two positive cubes in n distinct ways, up to order of summands. A brief history of taxicab numbers is given, along with a description of the computer search used by the author to find the 5th taxicab number, 48988659276962496. Additional results from the search are summarized.

1. Introduction

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 n-way sums). This guarantees the existence of a least n-way sum (that is, the nth taxicab number) for n >= 1, however, the construction given in [HW54] is of no help in finding the least n-way sum.

The first taxicab number is trivially

Ta(1) = 2
= 13 + 13.

The second taxicab number was first published by Frénicle de Bessy in 1657:

Ta(2) = 1729
= 13 + 123
= 93 + 103.

This particular number was immortalized by the following well-known 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 taxi-cab 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 Hardy-Ramanujan number for the number 1729, arose from this incident.

Subsequent taxicab numbers were discovered by computer search. In 1957, Leech obtained

Ta(3) = 87539319
= 1673 + 4363
= 2283 + 4233
= 2553 + 4143,

and in 1991 Rosenstiel, Dardis, and Rosenstiel [RDR91] found

Ta(4) = 6963472309248
= 24213 + 190833
= 54363 + 189483
= 102003 + 180723
= 133223 + 166303.

This paper announces the author's discovery, in November 1997, of the fifth taxicab number

Ta(5) = 48988659276962496
= 387873 + 3657573
= 1078393 + 3627533
= 2052923 + 3429523
= 2214243 + 3365883
= 2315183 + 3319543.

The taxicab numbers form sequence A011541 in [OEIS].

2. Background

An n-way sum is an integer s which can be expressed as the sum of two cubes in exactly n different ways, i.e:

s  =  a13 + b13  =  a23 + b23  =  ...  =  an3 + bn3.

where ai <= bi for 1 < i < n. Without loss of generality, we assume a1a2 < ... < an.

A primitive n-way sum is an n-way sum for which the ai and bi taken together have no common factor. If an n-way sum is non-primitive, it can be divided by gcd(a1, b1, a2, b2, ..., an, bn)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 n-way sums from known ones. I call these techniques combination and magnification.

The combination technique

The combination technique is used to combine two primitive n-way 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 = cd3. 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 n-way sums, both sums must have the same cubefree part. Let s and s´ be n-way sums with cubefree part c. Then we have

s  =  cd3  =  a13 + b13  =  a23 + b23  =  ...  =  an3 + bn3
s´  =  cd´3  =  a1´3 + b1´3  =  a2´3 + b2´3  =  ...  =  an´3 + bn´3.

These can be combined to give

s´´  =  c(dd´)3
      =  sd´3  =  (a1d´)3 + (b1d´)3  =  (a2d´)3 + (b2d´)3  =  ...  =  (and´)3 + (bnd´)3
      =  s´d3  =  (a1´d)3 + (b1´d)3  =  (a2´d)3 + (b2´d)3  =  ...  =  (an´d)3 + (bn´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 n-way 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 3-way sums:

327763000  =  3003 + 6703  =  3393 + 6613  =  5103 + 5803
26059452841  =  4173 + 29623  =  12903 + 28813  =  21933 + 24943

327763000 and 26059452841 each have the cubefree part 327763, which means that these sums can be combined. We obtain

26059452841000
      =  327763000·433  =  (300·43)3 + (670·43)3  =  (339·43)3 + (661·43)3  =  (510·43)3 + (580·43)3
      =  26059452841·103  =  (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 4-way sum:

26059452841000 = 41703 + 296203 = 129003 + 288103 = 145773 + 284233 = 219303 + 249403.

The magnification technique

The magnification technique is used to obtain a primitive (n+1)-way sum from a primitive n-way sum.

The idea is simple. If we have a primitive n-way sum

s  =  a13 + b13  =  a23 + b23  =  ...  =  an3 + bn3

we know that every cubic multiple of that sum will also be a (non-primitive) n-way sum:

sd3   =  (a1d)3 + (b1d)3  =  (a2d)3 + (b2d)3  =  ...  =  (and)3 + (bnd)3.

For some fortunate choice of multiple d3, we might hope for the serendipitous appearance of a new representation:

sd3   =  (a1d)3 + (b1d)3  =  (a2d)3 + (b2d)3  =  ...  =  (and)3 + (bnd)3  =  a´3 + b´3.

It turns out that often enough this hope is justified. For example, starting again with the 3-way sum

327763000  =  3003 + 6703  =  3393 + 6613  =  5103 + 5803,

we multiply 327763000 successively by d3  = 13, 23, 33, etc, each time checking for a new representation. Finally, at d3 = 433, an unexpected(?) solution arises:

327763000·433  =  (300·43)3 + (670·43)3  =  (339·43)3 + (661·43)3  =  (510·43)3 + (580·43)3  = 41703 + 296203,

and we have found the 4-way sum 26059452841000.

From a computational standpoint, exploiting the magnification technique to find n-way 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 = a3 + b3 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 = a3 + b3, using some known favorable properties of s.

First, we note that s is of the form

s = (cube)·(n-way sum)

We know the cube factor beforehand. The n-way sum factor by definition has n distinct representations as a3 + b3 = (a + b)(a2 - ab + b2), that is, n distinct representations as a product of two integers. From this observation we conclude that n-way sums should be highly factorable (for example, the 3-way sum 327763000 = 23·53·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 = a3 + b3:

It is not hard to show that this method generates all solutions to s = a3 + b3.

3. The Search for Ta(5)

The search for the fifth taxicab number arose from an attempt to extend sequence A003826 of [OEIS], the sequence of primitive 4-way 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 n-way sums. The program was written in the C programming language with 64-bit 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 = a3 + b3) 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 (a1b1s), (a2b2s), ..., (anbns) in S indicates that s is the n-way sum

s  =  a13 + b13  =  a23 + b23  =  ...  =  an3 + bn3.

The run detection part is relatively easy, so the problem really devolves to the efficient generation of S. My algorithm was:

  1. Initialize priority queue Q to contain all triples of the form (a = k, b = k, s = 2k3) with 1 <= s < 264 (this avoids 64-bit overflow of s, and translates to 1 <= k < 221 = 2097152). Q assigns higher priority to triples with smaller values of s.
  2. Obtain triple (abs) with smallest s value (high priority element) from Q.
  3. Pass triple (abs) to the run detector.
  4. Let (abs) := (ab + 1, a3 + (b + 1)3).
  5. Add (abs) back into Q.
  6. Go to step 2.

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 n-way 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 4-way sums given in [RDR91], but was unable to find any new 4-way sums.

Some time later, I applied the combination technique discussed in section 2 to the n-way sums that had been computed by this first version of this program. This led me to discover the primitive 5-way sum

t = 490593422681271000
= 483693 + 7886313
= 2337753 + 7817853
= 2851203 + 7760703
= 5431453 + 6912953
= 5792403 + 6666303

Since Ta(5) <= t < 264, this discovery showed that Ta(5) could in principle be found using the same basic 64-bit 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 month-long 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 5-way sum 48988659276962496. On November 17, the program verified that this 5-way 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.

4. Search Results

The main product of my search for the Ta(5) was a exhaustive list of all 3, 4, and 5-way sums of two cubes less than 5·1016 (2-way sums were too numerous to record). The following table summarizes the counts of various types of n-way sums found in the search:

Table 1: Counts of n-way sums of two cubes
s = a13 + b13 = a23 + b23 = ... = an3 + bn3
s <= 5·1016

 
Type of sum n = 3 n = 4 n = 5
All
No constraints
16159 143 1
Primitive
gcd(a1, b1, a2, b2, ..., an, bn) = 1
1630 35 1
Coprime Pair
gcd(ai, bi) = 1 for some i
892 9 1
All Pairs Coprime
gcd(ai, bi) = 1 for all i
81 0 0
Prime Occurrence
ai or bi prime for some i
419 5 1
Prime Pair
ai, bi 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 3-way sums of two cubes, too many to include in this article. Instead, I have composed several small tables of selected 3-way sums.

81 3-way 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].

Table 2: 30 least 3-way sums of two cubes with all pairs coprime
s = a13 + b13 = a23 + b23 = a33 + b33
gcd(a1, b1) = gcd(a2, b2) = gcd(a3, b3) = 1
 
# s a1 b1 a2 b2 a3 b3
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 3-way sums of two cubes were found in which a prime pair occurs. Table 3 lists them all. Immediately it appears that a 3-way sum with a prime pair will not admit another coprime pair. I am hesitant to conjecture this, though, since the analogous assertion for 2-way sums is not true (e.g, 6058655748 = 613182331049316993 [K99] and 6507811154 = 31318673397318613 [H99]).

Table 3: 27 least 3-way sums of two cubes involving a prime pair
s = a13 + b13 = a23 + b23 = a33 + b33
ai and bi both prime for some i

 
# s a1 b1 a2 b2 a3 b3
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:

Table 4: Two least 3-way sums involving three primes
s = a13 + b13 = a23 + b23 = a33 + b33
Three of a1, b1, a2, b2, a3, b3 prime.
 
# s a1 b1 a2 b2 a3 b3
1 4895818255862163 58243 167486 86048 162091 115499 149704
2 40778727507646891 52742 343787 138464 336563 255650 288731

35 primitive 4-way 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 4-way 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 3-way sums do not admit other coprime pairs.

Table 5: 35 least primitive 4-way sums of two cubes
s = a13 + b13 = a23 + b23 = a33 + b33 = a43 + b43
gcd(a1, b1, a2, b2, a3, b3, a4, b4) = 1

 
# s a1 b1 a2 b2 a3 b3 a4 b4
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 5-way sum discovered directly by the search was, of course

Ta(5) = 48988659276962496
= 387873 + 3657573
= 1078393 + 3627533
= 2052923 + 3429523
= 2214243 + 3365883
= 2315183 + 3319543.

here colored to indicate primality. Surprisingly, this 5-way sum includes a prime pair, again confirming that a prime pair in a 3-way sum admits no other coprime pair.

On the lighter side, a single primitive 3-way sum was found containing only even digits, and one containing only odd digits:

24248680282008000
= 783003 + 2875203
= 2080593 + 2479413
= 2275203 + 2319003
  9539173995131151
= 73083 + 2120793
= 1293673 + 1946423
= 1605343 + 1754633

5. Other Results

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 5-way sums and a 6-way sum:

490593422681271000
= 483693 + 7886313
= 2337753 + 7817853
= 2851203 + 7760703
= 5431453 + 6912953
= 5792403 + 6666303
 

 

6355491080314102272
= 1031133 + 18522153
= 5804883 + 18331203
= 7887243 + 18033723
= 11507923 + 16905443
= 14620503 + 14782383
 

 

27365551142421413376
= 1677513 + 30133053
= 2653923 + 30127923
= 9443763 + 29822403
= 12831483 + 29338443
= 18721843 + 27502883
 

1199962860219870469632
= 5915433 + 106258653
= 9358563 + 106240563
= 33301683 + 105163203
= 66019123 + 96983843
= 83875503 + 84804183

111549833098123426841016
= 10740733 + 481379993
= 87878703 + 480403563
= 139509723 + 477443823
= 244501923 + 459364623
= 337844783 + 417912043

8230545258248091551205888
= 112393173 + 2018914353
= 177812643 + 2018570643
= 632731923 + 1998100803
= 859709163 + 1965675483
= 1254363283 + 1842692963
= 1593634503 + 1611279423

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 6-way sum.

 

 

References

[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 = x3 + y3 = z3 + w3 = u3 + v3 = m3 + n3, Bull. Inst. Math. Appl., 27(1991) 155-157; 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.


Return to Journal of Integer Sequences home page