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

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

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

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

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

2. Background

s  =  a₁³ + b₁³  =  a₂³ + b₂³  =  ...  =  a_n³ + b_n³.

where a_i <= b_i for 1 < i < n. Without loss of generality, we assume a₁ < a₂ < ... < a_n.

A primitive n-way sum is an n-way sum for which the a_i and b_i taken together have no common factor. If an n-way sum is non-primitive, it can be divided by gcd(a₁, b₁, a₂, b₂, ..., a_n, b_n)³, 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 = cd³. 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  =  cd³  =  a₁³ + b₁³  =  a₂³ + b₂³  =  ...  =  a_n³ + b_n³
s´  =  cd´³  =  a₁´³ + b₁´³  =  a₂´³ + b₂´³  =  ...  =  a_n´³ + b_n´³.

These can be combined to give

s´´  =  c(dd´)³
      =  sd´³  =  (a₁d´)³ + (b₁d´)³  =  (a₂d´)³ + (b₂d´)³  =  ...  =  (a_nd´)³ + (b_nd´)³
      =  s´d³  =  (a₁´d)³ + (b₁´d)³  =  (a₂´d)³ + (b₂´d)³  =  ...  =  (a_n´d)³ + (b_n´d)³

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  =  300³ + 670³  =  339³ + 661³  =  510³ + 580³
26059452841  =  417³ + 2962³  =  1290³ + 2881³  =  2193³ + 2494³

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

26059452841000
      =  327763000·43³  =  (300·43)³ + (670·43)³  =  (339·43)³ + (661·43)³  =  (510·43)³ + (580·43)³
      =  26059452841·10³  =  (417·10)³ + (2962·10)³  =  (1290·10)³ + (2881·10)³  =  (2193·10)³ + (2494·10)³.

Out of six representations, four are distinct, and we obtain the 4-way sum:

26059452841000 = 4170³ + 29620³ = 12900³ + 28810³ = 14577³ + 28423³ = 21930³ + 24940³.

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  =  a₁³ + b₁³  =  a₂³ + b₂³  =  ...  =  a_n³ + b_n³

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

sd³   =  (a₁d)³ + (b₁d)³  =  (a₂d)³ + (b₂d)³  =  ...  =  (a_nd)³ + (b_nd)³.

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

sd³   =  (a₁d)³ + (b₁d)³  =  (a₂d)³ + (b₂d)³  =  ...  =  (a_nd)³ + (b_nd)³  =  a´³ + b´³.

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

327763000  =  300³ + 670³  =  339³ + 661³  =  510³ + 580³,

we multiply 327763000 successively by d³  = 1³, 2³, 3³, etc, each time checking for a new representation. Finally, at d³ = 43³, an unexpected(?) solution arises:

327763000·43³  =  (300·43)³ + (670·43)³  =  (339·43)³ + (661·43)³  =  (510·43)³ + (580·43)³  = 4170³ + 29620³,

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 = a³ + b³ 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³ + b³, 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 a³ + b³ = (a + b)(a² - ab + b²), 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 = 2³·5³·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³ + b³:

• Use trial division to obtain the prime factorization of s.
• Use the prime factorization to build a list of all factors of s.
• From this factor list, compose a list of all pairs (p, q) with p <= q and pq = s.
• For each pair (p, q) in the pair list, solve p = a + b and q = a² - ab+ b² for a and b.
• If a and b are both positive integers, then (a, b) solves s = pq  = (a + b)(a² - ab + b²)  = a³ + b³.

It is not hard to show that this method generates all solutions to s = a³ + b³.

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 = a³ + b³) 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₁, b₁, s), (a₂, b₂, s), ..., (a_n, b_n, s) in S indicates that s is the n-way sum

s  =  a₁³ + b₁³  =  a₂³ + b₂³  =  ...  =  a_n³ + b_n³.

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 = 2k³) with 1 <= s < 2⁶⁴ (this avoids 64-bit overflow of s, and translates to 1 <= k < 2²¹ = 2097152). Q assigns higher priority to triples with smaller values of s.
2. Obtain triple (a, b, s) with smallest s value (high priority element) from Q.
3. Pass triple (a, b, s) to the run detector.
4. Let (a, b, s) := (a, b + 1, a³ + (b + 1)³).
5. Add (a, b, s) 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

Since Ta(5) <= t < 2⁶⁴, 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·10¹⁶ (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:

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

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 = 61³ + 1823³ = 1049³ + 1699³ [K99] and 6507811154 = 31³ + 1867³ = 397³ + 1861³ [H99]).

Table 4 gives the two sums discovered involving three primes:

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.

The only 5-way sum discovered directly by the search was, of course

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:

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:

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

[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³ + y³ = z³ + w³ = u³ + v³ = m³ + n³, 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.