Seeds for Generalized Taxicab Numbers

Jeffrey H. Dinitz University of Vermont Burlington, VT 05405 USA

                  jeff.dinitz@uvm.edu

Richard A. Games Mitre Corporation Bedford, MA 01730 USA

                     rg@mitre.org

Robert L. Roth Department of Mathematics Emory University Atlanta, GA 30322 USA

                    laker@emory.edu

Abstract

The generalized taxicab number T (n, m, t) is equal to the smallest number that is the sum of n positive mth powers in t ways. This definition is inspired by Ramanujan’s observation that 1729 = 1^{3}+12^{3} = 9^{3}+10^{3} is the smallest number that is the sum of two cubes in two ways and thus 1729 = T (2, 3, 2). In this paper we prove that for any given positive integers m and t, there exists a number s such that T (s+k, m, t) = T (s, m, t)+k for every k ≥ 0. The smallest such s is termed the seed for the generalized taxicab number. Furthermore, we find explicit expressions for this seed number when the number of ways t is 2 or 3 and present a conjecture for t ≥ 4 ways.

1 Introduction

Hardy relays the following story about visiting Ramanujan during his illness (see [4, p. xxxv]):

I remember once going to see him when he was lying ill at Putney. I had ridden in taxi cab number 1729 and remarked that the number seemed to me rather a dull one, and that I hoped it was not an unfavorable omen. “No,” he replied, “it is a very interesting number; it is the smallest number expressible as the sum of two cubes in two different ways.”

Indeed, 1729 = 1^{3} + 12^{3} and 1729 = 9^{3} + 10^{3} and it is the smallest such number that is the sum of two cubes in two different ways. In honor of the Ramanujan–Hardy conversation, the smallest number expressible as the sum of two cubes in t different ways is known as the t^{th} taxicab number and is denoted Taxicab(t) . Therefore, with this notation, Taxicab(2) = 1729.

There has been considerable effort expended in finding these taxicab numbers. The interested reader is referred to [1] for information about these numbers. That paper contains interesting information about the history of the problem as well as a discussion about the techniques used to find certain values of Taxicab(t). Further information about taxicab numbers and their variants can also be found in [2, 3, 5, 6, 7]. Basically, Taxicab(t) is known for 2 ≤ t ≤ 6 and upper bounds for Taxicab(t) have been given for 7 ≤ t ≤ 22.

In this paper we generalize the definition of taxicab numbers, as there is really nothing special about using exactly two cubes (except for historical reasons). We will be concerned with finding the smallest number that is the sum of n positive m^{th} powers in at least t ways.

Let T (n, m, t) denote the least number that is the sum of n positive m^{th} powers in at least t ways provided such a number exists.^{1} The reason the definition above says that T (n, m, t) is the least number that is the sum of n positive m^{th} powers in at least t ways is motivated by the following equation

28 = 3^{3} + 3^{2} + 3^{2} + 1^{2} = 4^{2} + 2^{2} + 2^{2} + 2^{2} = 5^{2} + 1^{2} + 1^{2} + 1^{2}.

Indeed, 28 is the smallest number that is the sum of 4 squares in 2 ways as well as being the smallest number that is the sum of 4 squares in 3 ways. Hence we have that T (4, 2, 2) = 28 and also T (4, 2, 3) = 28. This is not the only example, in Section 4 we show T (8, 2, 4) = T (8, 2, 3) = 32.

So, as noted above, T (2, 3, 2) = 1729 and in general T (2, 3, t) is the taxicab number Taxicab(t). It is also easy to verify that

1It should be noted that in Wikipedia, the generalized taxicab number Taxicab(k, j, n) is the smallest number which can be expressed as the sum of j k^{th} positive powers in n different ways. However, since there have been no published papers with this notation, we use the notation in the definition given above.

T (2, 2, 2) = 50 = 5^{2} + 5^{2} = 7^{2} + 1
T (3, 2, 2) = 27 = 5^{2} + 1 + 1 = 3^{2} + 3^{2} + 3^{2}
T (4, 2, 2) = 28 = 5^{2} + 1 + 1 + 1 = 3^{2} + 3^{2} + 3^{2} + 1
T (5, 2, 2) = 20 = 4^{2} + 1 + 1 + 1 + 1 = 2^{2} + 2^{2} + 2^{2} + 2^{2} + 2^{2}.

Note that by adding 1 to the two sums in the last example we obtain

T (6, 2, 2) ≤ 21 = 4^{2} + 1 + 1 + 1 + 1 + 1 = 2^{2} + 2^{2} + 2^{2} + 2^{2} + 2^{2} + 1.

Doing this again we obtain

T (7, 2, 2) ≤ 22 = 4^{2} + 1 + 1 + 1 + 1 + 1 + 1 = 2^{2} + 2^{2} + 2^{2} + 2^{2} + 2^{2} + 1 + 1.

In fact it is indeed true that T (6, 2, 2) = 21 and T (7, 2, 2) = 22.

Considering cubes now, it is straightforward to verify that

T (2, 3, 2) = 1729 = 12^{3} + 1 = 10^{3} + 9^{3}
T (3, 3, 2) = 251 = 6^{3} + 3^{3} + 2^{3} = 5^{3} + 5^{3} + 1
T (4, 3, 2) = 219 = 6^{3} + 1 + 1 + 1 = 4^{3} + 4^{3} + 4^{3} + 3^{3}
T (5, 3, 2) = 157 = 5^{3} + 2^{3} + 2^{3} + 2^{3} + 2^{3} = 4^{3} + 4^{3} + 3^{3} + 1 + 1
T (6, 3, 2) = 158 = 5^{3} + 2^{3} + 2^{3} + 2^{3} + 2^{3} + 1 = 4^{3} + 4^{3} + 3^{3} + 1 + 1 + 1
T (7, 3, 2) = 131 = 5^{3} + 1 + 1 + 1 + 1 + 1 + 1 = 4^{3} + 3^{3} + 2^{3} + 2^{3} + 2^{3} + 2^{3} + 2^{3}
T (8, 3, 2) = 132 = 5^{3} + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 4^{3} + 3^{3} + 2^{3} + 2^{3} + 2^{3} + 2^{3} + 2^{3} + 1
T (9, 3, 2) = 72 = 4^{3} + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 2^{3} + 2^{3} + 2^{3} + 2^{3} + 2^{3} + 2^{3} + 2^{3} + 2^{3} + 2^{3}
T (10, 3, 2) = 73 = 4^{3} + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 =
2^{3} + 2^{3} + 2^{3} + 2^{3} + 2^{3} + 2^{3} + 2^{3} + 2^{3} + 2^{3} + 1.

One also can check that T (11, 3, 2) = 74 and that this solution results from adding 1 to both of the (equal) sums in the case of T (10, 3, 2).

From the examples above it seems plausible that there exists a number, say s_{0}, such that T (n + 1, m, t) = T (n, m, t) + 1 for all n ≥ s_{0} or equivalently, that T (s_{0} + k, m, t) = T (s_{0}, m, t) + k for all k ≥ 0 . This motivates the following definition.

Definition 1. If s_{0} is the smallest positive integer such that T (n + 1, m, t) = T (n, m, t) + 1 for all n ≥ s_{0}, then we call s_{0} the seed number for m^{th} powers in t ways and denote this number by S(m, t) = s_{0}. We also call T (S(m, t), m, t) the seed value of m^{th} powers in t ways and denote it by V (m, t).

This paper proceeds as follows. In Section 2 we show that for every m and t there exists a seed number. In Section 3 we give an explicit value for the seed of the sum of m^{th} powers in 2 ways. We prove there that the seed number for squares in 2 ways is indeed 5 and the seed value is 20. In our notation, this says S(2, 2) = 5 and V (2, 2) = 20 and hence T (5 + k, 2, t) = 20 + k for all k ≥ 0. In Section 4 we give an explicit value of V (m, 3). Finally, in Section 5, we give a general theorem and a conjecture about the seed for m^{th} powers in t ways for all t ≥ 2.

2 Seeds exist

In this section we prove that for every m and t there exists a seed number. We first show that for every m and t there exist some positive integer n and some value v such that v is the sum of n m^{th} powers in t ways. From that we then show that there is a least such n and hence there exists a seed number (and a seed value).

Lemma 2. For all positive integers m, t ≥ 1, there exist positive integers n and v such that v is the sum of n m^{th} powers in t ways.

Proof. If m = 1 or t = 1, the result is obvious, so assume that m, t > 1.

We give a direct construction of t different sums of m^{th} powers, each sum having the same number of terms. The first sum is t^{m} + t^{m} + ⋯ + t^{m} for a suitable number of terms. For each 1 ≤ i ≤ t − 1 we construct the sum S_{i} from the terms (t − i)^{m} and (t + i)^{m}. So

each S_{i} = \underbrace{(t − i)^{m} + ⋯ + (t − i)^{m}}_{x_{i}} + \underbrace{(t + i)^{m} + ⋯ + (t + i)^{m}}_{y_{i}} for suitable x_{i} and y_{i}.

In order to define the sums, we first need to define some values. For each 1 ≤ i ≤ t − 1 define

a_{i} = t^{m} − (t − i)^{m}  b_{i} = (t + i)^{m} − t^{m}  l_{i} = lcm(a_{i}, b_{i});
α_{i} = l_{i}/a_{i}  β_{i} = l_{i}/b_{i}  γ_{i} = α_{i} + β_{i}
n = lcm(γ_{1}, γ_{2}, …, γ_{t−1})  δ_{i} = n/γ_{i}.

Using these values, define

S_{0} = \underbrace{t^{m} + ⋯ + t^{m}}_{n}

and for each 1 ≤ i ≤ t − 1 define

S_{i} = \underbrace{(t − i)^{m} + ⋯ + (t − i)^{m}}_{α_{i}δ_{i}} + \underbrace{(t + i)^{m} + ⋯ + (t + i)^{m}}_{β_{i}δ_{i}} .

Obviously all of these sums are different (in fact no two sums contain any terms in common). We must prove two things: first, that each of the sums S_{0}, S_{1}, …, S_{t−1} contain the same number of terms and second, that S_{0} = S_{1} = ⋯ = S_{t−1}.

To show the first, we note that S_{0} contains n terms and for each 1 ≤ i ≤ t−1, S_{i} contains α_{i}δ_{i} + β_{i}δ_{i} terms. But now

α_{i}δ_{i} + β_{i}δ_{i} = (α_{i} + β_{i})δ_{i} = γ_{i}δ_{i} = n

as desired.

Next we compute the sums. Clearly S_{0} = nt^{m}. For each 1 ≤ i ≤ t − 1,

S_{i} = α_{i}δ_{i}(t − i)^{m} + β_{i}δ_{i}(t + i)^{m}

= (α_{i}(t^{m} − a_{i}) + β_{i}(t^{m} + b_{i}))δ_{i} = ((α_{i} + β_{i})t^{m} + (β_{i}b_{i} − α_{i}a_{i}))δ_{i} = ((α_{i} + β_{i})t^{m} + (l_{i} − l_{i}))δ_{i}

= γ_{i}t^{m} \frac{n}{γ_{i}}

= nt^{m}.

Thus we conclude that S_{0} = S_{1} = ⋯ = S_{t−1} = nt^{m}. This completes the proof.

By adding a 1 to each multiset of terms in the above sums, we see that T (n + 1, m, t) ≤ T (n, m, t)+1.

As an immediate consequence of this observation and Lemma 2 we can conclude that T (n, m, t) exists for every m, t ≥ 1 when n is large enough. In general, we do not know whether T (n, m, t) exists for all n less than the value of n(= lcm(γ_{1}, γ_{2}, …, γ_{t−1})) given above.

In the next theorem we prove that there is a seed number for every m and t.

Theorem 3. For every m, t ≥ 1, there is a smallest number s_{0} such that T (s_{0} + k, m, t) = T (s_{0}, m, t) + k for every k ≥ 0. Hence for every m, t ≥ 1 the seed number s_{0} = S(m, t) exists.

Proof. Fix m and t. Note that for some n large enough, T (n, m, t) exists by Lemma 2. Now let n_{0} be the smallest integer for which T (n_{0}, m, t) exists.

To shorten notation let T′(n) = T (n, m, t). Notice that for any n, a (very naive) lower bound for T′(n) is n since

T′(n) ≥ \underbrace{1^{m} + 1^{m} + ⋯ + 1^{m}}_{n} = n.

The gap between the value of T′(n_{0}) and the naive lower bound on T′(n_{0}) is g = T′(n_{0})−n_{0} ≥ 0. We also have that T′(n_{0} + k) ≤ T′(n_{0}) + k for every k ≥ 0. Thus n_{0} + k ≤ T′(n_{0} + k) ≤ T′(n_{0}) + k.

We say that the function T′ drops at n if T′(n+1) < T′(n)+1 (note that n is the location of the “drop” and not the amount T′ drops). Let D = {n ≥ n_{0} | T′(n + 1) < T′(n) + 1} be the set of all drops of T′. We claim that D is a finite set and in fact we show that |D| ≤ g.

Let D = {n_{1}, n_{2}, …}. (We should note that possibly D = ∅, in which case S(m, t) is just n_{0}.) If D is nonempty, say that n_{k} = n_{0} + x_{k}, then we see that since T′ is dropped by at least one at each n_{i} we have

T′(n_{k} + 1) = T′(n_{0} + x_{k} + 1) ≤ T′(n_{0}) + x_{k} + 1 − k.

So since n_{0}+x_{k} +1 ≤ T′(n_{0}+x_{k} +1), we have n_{0} ≤ T′(n_{0})−k and hence k ≤ T′(n_{0})−n_{0} = g. This implies that |D| ≤ g and hence there are at most g drops in the function T′. So if D = {n_{1}, n_{2}, … n_{i}} is the set of all drops, then since n_{i} is the last drop in the function T′, we have T′(n_{i} + 1 + k) = T′(n_{i} + 1) + k for all k ≥ 0 and hence n_{i} + 1 is the seed number S(m, t).

As an example of the above theorem we consider the values of T (2, 3, 2), T (3, 3, 2), …, T (10, 3, 2) given in Section 1. Notice that n_{0} = 2 since T (2, 3, 2) = 1729 (and clearly T(1,3,2) does not exist). We also see that n_{1} = 2, n_{2} = 3, n_{3} = 4, n_{4} = 6, and n_{5} = 8. We prove in Section 4 that indeed D = {2, 3, 4, 6, 8}. Thus we conclude that S(3, 2) = 9 and hence T (9 + k, 3, 2) = T (9, 3, 2) + k = 72 + k for all k ≥ 0.

3 Seeds for two ways

In this section we give the explicit value for the seed numbers for two ways. We assume that all variables are positive integers except where noted. We begin with three easy lemmas that hold for any number of sums. The first lemma says that if all the sums share a common term, then that term must be equal to 1.

Lemma 4. If x = T (n, m, t) and x = ∑_{i=1}^{n} a_{i}^{m} = ∑_{i=1}^{n} b_{i}^{m} = ⋯ = ∑_{i=1}^{n} t_{i}^{m}, and if a_{i_{1}} = b_{i_{2}} = ⋯ = t_{i_{t}} for some choice of i′s, then a_{i_{1}} = b_{i_{2}} = ⋯ = t_{i_{t}} = 1.

Proof. If not, then replace each of a_{i_{1}}, b_{i_{2}}, …, t_{i_{t}} with a 1 and get a contradiction to x = T (n, m, t) since the new sums of the m^{th} powers are still the same and less than before, a contradiction.

The next lemma says that the t sums adding to the seed value can’t all have a 1 as a term.

Lemma 5. If x = V (m, t) and x = ∑_{i=1}^{n} a_{i}^{m} = ∑_{i=1}^{n} b_{i}^{m} = ⋯ = ∑_{i=1}^{n} t_{i}^{m}, and if a_{i_{1}} = b_{i_{2}} = ⋯ = t_{i_{t}} for some choice of i′s, then a_{i_{1}} = b_{i_{2}} = ⋯ = t_{i_{t}} ≠ 1.

Proof. If each sum has a 1 as a term, then by simply deleting the 1 in each of these sums we would obtain a smaller seed value, a contradiction.

In the next lemma we show that any seed value for m^{th} powers in t ways must always be greater or equal to n2^{m} where n is the seed number. This essentially says that we can always assume that one of the sums is

\underbrace{2^{m} + 2^{m} + ⋯ + 2^{m}}_{n} .

This fact is of fundamental importance in finding seeds for 2 and 3 ways.

Lemma 6. If V (m, t) = ∑_{i=1}^{s_{0}} a_{i}^{m} = ∑_{i=1}^{s_{0}} b_{i}^{m} = ⋯ = ∑_{i=1}^{s_{0}} t_{i}^{m} is the seed value for m^{th} powers in t ways, then V (m, t) ≥ s_{0}2^{m}. Further, if n is any number which provides a solution to ∑_{i=1}^{n} a_{i}^{m} = ∑_{i=1}^{n} b_{i}^{m} = ⋯ = ∑_{i=1}^{n} t_{i}^{m} = n2^{m}, then V (m, t) = s_{0}2^{m}, where s_{0} is the smallest such n (and hence s_{0} = S(m, t)).

Proof. Let V (m, t) = ∑_{i=1}^{s_{0}} a_{i}^{m} = ∑_{i=1}^{s_{0}} b_{i}^{m} = ⋯ = ∑_{i=1}^{s_{0}} t_{i}^{m} be the seed value for m^{th} powers in t ways and assume that each sum is written in nonincreasing order.

Now if a_{s_{0}} = 1, then from Lemma 5 we have without loss of generality that b_{s_{0}} ≠ 1. Thus for all 1 ≤ i ≤ s_{0} it must be that b_{i} ≥ 2. Hence in this case we have V (m, t) ≥ s_{0}2^{m}. If a_{s_{0}} ≥ 2, then since a_{i} ≥ a_{i+1} for all 1 ≤ i ≤ s_{0} − 1, then clearly V (m, t) ≥ s_{0}2^{m}.

The second part of this lemma now follows immediately.

Lemma 6 implies that the seed value is the sum of s_{0} 2^{m}’s (where s_{0} are equal to the seed number S(m, t)). So we are interested in this value for the sum. In the next two lemmas we consider two different sums that are equal to the sum of 2^{m}’s. The verification of the first is a straightforward calculation.

Lemma 7. If α4^{m} + (n − α) = n2^{m}, then n = (2^{m} + 1)α and hence n ≥ 2^{m} + 1.

A comment is in order concerning Lemma 7. This lemma deals with the case when two sums are equal and one of the sums is all 2^{m}’s while the other is 4^{m}’s and 1^{m}’s. Specifically, it says that if

\underbrace{4^{m} + 4^{m} + ⋯ + 4^{m}}_{α} + \underbrace{1 + 1 + ⋯ + 1}_{n−α} = \underbrace{2^{m} + 2^{m} + ⋯ + 2^{m}}_{n},

then n ≥ 2^{m} + 1. The next lemma deals with the case when two sums are equal and one of the sums is all 2^{m}’s and the other is 3^{m}’s and 1^{m}’s.

Lemma 8. If α3^{m} + (n − α) = n2^{m} and if d = gcd(3^{m} − 2^{m}, 2^{m} − 1), then \frac{3^{m}−1}{d} | n and hence n ≥ \frac{3^{m}−1}{d}.

Proof. Assume that α3^{m} + (n − α) = n2^{m} and that d = gcd(3^{m} − 2^{m}, 2^{m} − 1). Then

α (\frac{3^{m} − 1}{d}) = n (\frac{2^{m} − 1}{d}) .

Now since d = gcd(3^{m} − 2^{m}, 2^{m} − 1) = gcd(3^{m} − 1, 2^{m} − 1), then 1 = gcd(\frac{3^{m}−1}{d}, \frac{2^{m}−1}{d}) and thus we have \frac{2^{m}−1}{d} | α. So α(\frac{d}{2^{m}−1}) is an integer. Now since α(\frac{d}{2^{m}−1}) (\frac{3^{m}−1}{d}) = n it follows that (\frac{3^{m}−1}{d}) | n and hence n ≥ \frac{3^{m}−1}{d}.

The application of this lemma is similar to that of Lemma 7. In this case we have the situation where

\underbrace{3^{m} + 3^{m} + ⋯ + 3^{m}}_{α} + \underbrace{1 + 1 + ⋯ + 1}_{n−α} = \underbrace{2^{m} + 2^{m} + ⋯ + 2^{m}}_{n} .

So here we have that n = α(\frac{d}{2^{m}−1}) (\frac{3^{m}−1}{d}) and our main application is that in this case n ≥ \frac{3^{m}−1}{d}.

We now obtain our characterization of the seed number and the seed value for sums in two ways.

Theorem 9. Let d = gcd(3^{m} −2^{m}, 2^{m} −1). The seed number S(m, 2) = min(\frac{3^{m}−1}{d}, 2^{m} +1) = s_{0} and the seed value V (m, 2) = s_{0}2^{m}. Hence T (s_{0} + j, m, 2) = s_{0}2^{m} + j for every j ≥ 0.

Proof. Consider the two equations

4^{m} + \underbrace{1 + ⋯ + 1}_{2^{m}} = \underbrace{2^{m} + ⋯ + 2^{m}}_{2^{m}+1} = (2^{m} + 1)2^{m}  (1)

and

\underbrace{3^{m} + ⋯ + 3^{m}}_{\frac{2^{m}−1}{d}} + \underbrace{1 + ⋯ + 1}_{\frac{3^{m}−2^{m}}{d}} = \underbrace{2^{m} + ⋯ + 2^{m}}_{\frac{3^{m}−1}{d}} = (\frac{3^{m} − 1}{d})2^{m}.  (2)

In view of Equations (1) and (2) and Lemma 6, if V (m, t) = a_{1}^{m} + a_{2}^{m} + ⋯ + a_{n}^{m} = b_{1}^{m} + b_{2}^{m} + ⋯ + b_{n}^{m} is the seed value for m^{th} powers in 2 ways, then we can assume that b_{i} = 2 for all i. We next show that a_{1} ≤ 4.

Assume that V (m, t) = a_{1}^{m} + a_{2}^{m} + ⋯ + a_{n}^{m} = 2^{m} + 2^{m} + ⋯ + 2^{m} is the seed value for m^{th} powers in 2 ways with a_{i} ≥ a_{i+1} for all 1 ≤ i ≤ n − 1.

Assume that a_{1} ≥ 5. Clearly, if n ≥ 2^{m} + 1, then in view of Equation (1) above this is a contradiction (since a_{1}^{m} + a_{2}^{m} + ⋯ + a_{n}^{m} > 4^{m} + 1 + ⋯ + 1). Assume n < 2^{m} + 1, then

a_{1}^{m} + a_{2}^{m} + ⋯ + a_{n}^{m} + \underbrace{1 + 1 + ⋯ + 1}_{2^{m}+1−n} > 4^{m} + \underbrace{1 + ⋯ + 1}_{2^{m}}

which is again a contradiction to the assumption that V (m, t) = a_{1}^{m}+a_{2}^{m}+⋯+a_{n}^{m}. Assuming that a_{1} = 4 and a_{2} > 1 yields a similar contradiction.

So either {a_{1}, a_{2}, … a_{n}} = {1, 4} or {a_{1}, a_{2}, … a_{n}} = {1, 3} since by Lemma 4 no a_{i} can be equal to any b_{i} = 2. In the first case we obtain Equation (1) since no smaller sum can have only 4^{m}’s and 1’s as its terms. In the second case we can assume that s3^{m} + (n − s) = n2^{m} for some s.

From Lemma 8, the minimum value of n is \frac{3^{m}−1}{d}, which leads to Equation (2). The seed number is therefore be the minimum length of the sums in either Equation (1) or Equation (2). Thus the minimum of 2^{m} + 1 and \frac{3^{m}−1}{d} is the seed number S(m, 2).

In Table 3 we compute seeds for m^{th} powers in 2 ways for m ≤ 20.

The interested reader may note that S(m, 2) = 2^{m} + 1 in every case above except when m = 1, 4, 12. This says that 2^{m} + 1 ≤ (3^{m} − 1)/d for every m ≤ 20 with m ≠ 1, 4, 12. We computed values of 2^{m} + 1 and (3^{m} − 1)/d for all m ≤ 200, 000 and found that 2^{m} + 1 ≤ (3^{m} − 1)/d for all m in that range except for m = 1, 4, 12 and 36. We do not conjecture that this is true for all m > 36; however, it certainly appears to be true.

In Table 3 we give explicit values from Theorem 9. Remember that S(m, 2) is the number of terms in the seed, while V (m, 2) is the exact value of the seed.

\begin{matrix}m & d & S(m, 2) & V (m, 2) \\ 1 & 1 & 2 & 4 \\ 2 & 1 & 5 & 20 \\ 3 & 1 & 9 & 72 \\ 4 & 5 & 16 & 256 \\ 5 & 1 & 33 & 1056 \\ 6 & 7 & 65 & 4160 \\ 7 & 1 & 129 & 16512 \\ 8 & 5 & 257 & 65792 \\ 9 & 1 & 513 & 262656 \\ 10 & 11 & 1025 & 1049600 \\ 11 & 23 & 2049 & 4196352 \\ 12 & 455 & 1168 & 4784128 \\ 13 & 1 & 8193 & 67117056 \\ 14 & 1 & 16385 & 268451840 \\ 15 & 1 & 32769 & 1073774592 \\ 16 & 85 & 65537 & 4295032832 \\ 17 & 1 & 131073 & 17180000256 \\ 18 & 133 & 262145 & 68719738880 \\ 19 & 1 & 524289 & 274878431232 \\ 20 & 275 & 1048577 & 1099512676352 \end{matrix}

Table 1: Seed values and size

4 Seeds for three ways

In this section we give an explicit value for V (m, 3), the seed value for the smallest number that can be written as the sum of m^{th} powers in 3 ways.

We first need a preliminary lemma which says that no term in a sum that is a seed value (for powers m ≥ 4) can exceed the number 4.

Lemma 10. The seed value V (m, 3) = ∑_{i=1}^{s} a_{i}^{m} = ∑_{i=1}^{s} b_{i}^{m} = s2^{m} where s = S(m, 3) is the seed number. If m ≥ 4, then a_{i}, b_{i} ≤ 4 for all 1 ≤ i ≤ s.

Proof. We first note the following equalities:

\begin{aligned}\underbrace{4^{m} + 1 + ⋯ + 1}_{2^{m}+1} + \underbrace{4^{m} + 1 + ⋯ + 1}_{2^{m}+1} & = \underbrace{4^{m} + 1 + ⋯ + 1}_{2^{m}+1} + \underbrace{2^{m} + ⋯ + 2^{m}}_{2^{m}+1} \\ & = \underbrace{2^{m} + ⋯ + 2^{m}}_{2^{m}+1} + \underbrace{2^{m} + ⋯ + 2^{m}}_{2^{m}+1} . \end{aligned}  (3)

From this equation and Lemma 6 we have V (m, 3) = s2^{m} for s = S(m, 3). We also see from this equation

that the taxicab number T (2(2^{m}+1)+j, m, 3) ≤ 2(2^{m}+1)2^{m}+j for all j ≥ 0 and that the seed number S(m, 3) ≤ 2(2^{m} +1). So in particular, when j = 0 we have T (2(2^{m} +1), m, 3) ≤ 2(2^{m} + 1)2^{m}.

Now, assume V (m, 3) = ∑_{i=1}^{s} a_{i}^{m} = ∑_{i=1}^{s} b_{i}^{m} = s2^{m} where s = S(m, 3) is the seed number. Then s ≤ 2(2^{m} + 1). Assume that a_{1} ≥ 5. Since a_{i} ≥ 1 for all i > 1, when extending the sums to have 2(2^{m} + 2) terms by adding sufficiently many 1’s, we get

5^{m} + 2(2^{m} + 1) − 1 ≤ ∑_{i=1}^{s} a_{i}^{m} + (2(2^{m} + 1) − s) ≤ T (2(2^{m} + 1), m, 3)

and hence

5^{m} + 2(2^{m} + 1) − 1 ≤ T (2(2^{m} + 1), m, 3) ≤ 2(2^{m} + 1)2^{m}.

Thus

5^{m} + 2(2^{m} + 1) − 1 ≤ 2(2^{m} + 1)2^{m}
≤ (2^{m} + 1)2^{m+1}

and hence

5^{m} ≤ 2^{m} + 1)(2^{m+1} − 2) + 1
≤ 2^{2m+1} − 1
≤ 2 × 4^{m} − 1.

This last inequality implies m = 1, 2, or 3, but by hypothesis m ≥ 4, so we obtain a contradiction. Hence a_{i} ≤ 4 (similarly b_{i} ≤ 4) for all 1 ≤ i ≤ s.

We are now in position to obtain our characterization of the seed number and the seed value for sums in three ways. We begin with the small values of m.

Theorem 11. (a) S(1, 3) = 3 and the seed value V (1, 3) = 3 × 2^{1} = 6,

(b) S(2, 3) = 8 and the seed value V (2, 3) = 8 × 2^{2} = 32, (c) S(3, 3) = 18 and the seed value V (3, 3) = 18 × 2^{3} = 144.

Proof. The sums are given below. It is straightforward to check that they are minimal.

(a) 6 = 4 + 1 + 1 = 3 + 2 + 1 = 2 + 2 + 2.

(b) 32 = 4^{2} + 2^{2} + 2^{2} + 2^{2} + 1 + 1 + 1 + 1 = 3^{2} + 3^{2} + 3^{2} + 1 + 1 + 1 + 1 + 1 = \underbrace{2^{2} + ⋯ + 2^{2}}_{8} .

(c) 144 = 4^{3} + 4^{3} + \underbrace{1 + ⋯ + 1}_{16} = 4^{3} + \underbrace{1 + ⋯ + 1}_{8} + \underbrace{2^{3} + ⋯ + 2^{3}}_{9} = \underbrace{2^{3} + ⋯ + 2^{3}}_{18} .

Theorem 12. Assume that m ≥ 4 and let d = gcd(3^{m} − 2^{m}, 2^{m} − 1). Also let l_{3} = \frac{3^{m}−1}{d} and l_{4} = 2^{m} + 1.

Given the four values l_{3}, l_{4}, 2l_{3}, 2l_{4}, the second smallest of these values is the seed number S(m, 3) and the seed value V (m, 3) = S(m, 3) × 2^{m}. Remark 13. Then

1. if 2l_{4} < l_{3}, then the seed number S(m, 3) = 2l_{4} and the seed value V (m, 3) = 2l_{4}2^{m}.

2. if l_{3} ≤ l_{4} ≤ 2l_{3}, then the seed number S(m, 3) = l_{4} and the seed value V (m, 3) = l_{4}2^{m},

3. if l_{4} < l_{3} ≤ 2l_{4}, then the seed number S(m, 3) = l_{3} and the seed value V (m, 3) = l_{3}2^{m},

4. if 2l_{3} < l_{4}, then the seed number S(m, 3) = 2l_{3} and the seed value V (m, 3) = 2l_{3}2^{m}, Proof. Considering Equation (3) in the proof of Lemma 10, in all cases the seed number S(m, 3) ≤ 2l_{4}. Also, we can assume that the seed value V (m, 3) = ∑_{i=1}^{s} a_{i}^{m} = ∑_{i=1}^{s} b_{i}^{m} = s2^{m} where s = S(m, 3) is the seed number and (from Lemma 10) a_{i}, b_{i} ≤ 4 for all i. Let A = {a_{1}, a_{2}, …, a_{s}} = {1^{α_{1}}, 2^{α_{2}}, 3^{α_{3}}, 4^{α_{4}}} be the multiset containing all the terms in the sum ∑_{i=1}^{s} a_{i}^{m} (so A contains the term i^{m} exactly α_{i} times for 1 ≤ i ≤ 4), and let B = {b_{1}, b_{2}, …, b_{s}} = {1^{β_{1}}, 2^{β_{2}}, 3^{β_{3}}, 4^{β_{4}}} be the multiset containing the terms in the sum ∑_{i=1}^{s} b_{i}^{m}. From Lemma 4 we can assume without loss of generality that β_{2} = 0, since it can not be the case that both an a_{i} = 2 and a b_{j} = 2, so we can assume that β_{2} = 0.

There are four cases to consider, depending on which of the four values in the statement of the theorem is the second smallest value. Remark 14. Case 1: 2l_{4} is the second smallest value; Case 2: l_{4} is the second smallest value; Case 3: l_{3} is the second smallest value; Case 4: 2l_{3} is the second smallest value.

Case 1. 2l_{4} is the second smallest value. This assumption implies 2l_{4} ≤ l_{3}. Assume s = S(m, 3) < 2l_{4}. We see first that 0 ≤ α_{4}, β_{4} ≤ 1, since if (say) α_{1} ≥ 2, then ∑_{i=1}^{s} a_{i}^{m} ≥ 4^{m} + 4^{m} + (s − 2)1^{m} and so ∑_{i=1}^{s} a_{i}^{m} + (2l_{4} − s) ≥ 4^{m} + 4^{m} + (2l_{4} − 2) which (because of Equation (3)) says ∑_{i=1}^{s} a_{i}^{m} can not be a seed value unless α_{3} = α_{2} = 0 in which case we are led to one of the sums in Equation (3). However since we assumed s < 2l_{4}, this is a contradiction.

Now, if β_{4} = 0 we obtain the equation β_{3}3^{m} + β_{1}1^{m} = s2^{m}. By Lemma 8 we thus have s ≥ l_{3}. So s ≥ l_{3} > 2l_{4} > s a contradiction. If α_{4} = 0, then by subtracting α_{2} 2^{m}’s from each side of the equation ∑_{i=1}^{s} a_{i}^{m} = s2^{m} we obtain a similar contradiction. Hence we can assume that α_{4} = β_{4} = 1.

So we have

4^{m} + α_{3}3^{m} + α_{2}2^{m} + α_{1}1^{m} = 4^{m} + β_{3}3^{m} + β_{1}1^{m}

subtracting 4^{m} from both sides yields

α_{3}3^{m} + α_{2}2^{m} + α_{1}1^{m} = β_{3}3^{m} + β_{1}1^{m}.

This implies that

α_{2}2^{m} = (β_{3} − α_{3})3^{m} + (β_{1} − α_{1}).

Now since (β_{3} − α_{3}) + (β_{1} − α_{1}) = α_{2} and since α_{2} > 0 (else the equation is degenerate), then by Lemma 8 we have α_{2} ≥ l_{3}, a clear contradiction.

So in this case we have s ≥ 2l_{4}. Equation (3) then proves that indeed in this case s = S(m, 3) = 2l_{4} and hence the seed value V (m, 3) = 2l_{4}2^{m}.

Case 2. l_{4} is the second smallest value. This assumption implies l_{3} ≤ l_{4} ≤ 2l_{3}. First consider the following equation:

\underbrace{4^{m} + 1 + ⋯ + 1}_{l_{4}} = \underbrace{3^{m} + ⋯ + 3^{m}}_{(2^{m}−1)/d)} + \underbrace{1^{m} + ⋯ + 1^{m}}_{(3^{m}−2^{m})/d)} + \underbrace{2^{m} + ⋯ + 2^{m}}_{l_{4}−l_{3}} = \underbrace{2^{m} + ⋯ + 2^{m}}_{l_{4}} . (4)

From this equation we see that in this case s = S(m, 3) ≤ l_{4}. Assume s = S(m, 3) < l_{4}.

If α_{4} ≥ 1 (or β_{4} ≥ 1), then ∑_{i=1}^{s} a_{i}^{m} ≥ 4^{m} + (s − 1)1^{m} and so ∑_{i=1}^{s} a_{i}^{m} + (l_{4} − s) ≥ 4^{m} + (l_{4} − 1) which (because of Equation (4) says ∑_{i=1}^{s} a_{i}^{m} can not be a seed value, unless α_{3} = α_{2} = 0 in which case we are led to the first sum in Equation (4). However, since we assumed that s < l_{4} we see that this is a contradiction. So α_{4} = β_{4} = 0. Hence

α_{3}3^{m} + α_{2}2^{m} + α_{1}1^{m} = β_{3}3^{m} + β_{1}1^{m} = s2^{m}  (5)

and subtracting α_{3}3^{m} and α_{1}1^{m} from the first two sums yields

α_{2}2^{m} = (β_{3} − α_{3})3^{m} + (β_{1} − α_{1})1^{m}

and so by Lemma 8 we have α_{2} ≥ l_{3}. Also, subtracting α_{2}2^{m} from the first and third sums in Equation (5) we have

α_{3}3^{m} + α_{1}1^{m} = (s − α_{2})2^{m}.

So, again by Lemma 8 we have s − α_{2} = α_{1} + α_{3} ≥ l_{3}. Thus s = α_{1} + α_{2} + α_{3} ≥ 2l_{3}, a clear contradiction to our assumption that s < l_{4} ≤ 2l_{3}.

So in this case we have s ≥ l_{4}. Equation (4) then proves that in this case s = S(m, 3) = l_{4} and hence the seed value V (m, 3) = l_{4}2^{m}.

Case 3. l_{3} is the second smallest value. So in this case l_{4} ≤ l_{3} ≤ 2l_{4}. First note the following equation:

\underbrace{4^{m} + 1 + ⋯ + 1}_{l_{4}} + \underbrace{2^{m} + ⋯ + 2^{m}}_{l_{3}−l_{4}} = \underbrace{3^{m} + ⋯ + 3^{m}}_{(2^{m}−1)/d)} + \underbrace{1^{m} + ⋯ + 1^{m}}_{(3^{m}−2^{m})/d)} = \underbrace{2^{m} + ⋯ + 2^{m}}_{l_{3}} . (6)

From this we see that s = S(m, 3) ≤ l_{3}. Assume s = S(m, 3) < l_{3} and consider T (2l_{4}, m, 3). We see that T (2l_{4}, m, 3) = ∑_{i=1}^{s} a_{i}^{m} + (2l_{4} − s) < 2l_{4}2^{m} since ∑_{i=1}^{s} a_{i}^{m} is the seed value and l_{3} ≤ 2l_{4}. However, if α_{4} ≥ 2 (or β_{4} ≥ 2), then T (2l_{4}, m, 3) ≥ 4^{m} + 4^{m} + (l_{4} − 2)1^{m} = 2l_{4}2^{m}, a contradiction.

So we can assume 0 ≤ α_{4}, β_{4} ≤ 1. We have

α_{4}4^{m} + α_{3}3^{m} + α_{2}2^{m} + α_{1}1^{m} = β_{4}4^{m} + β_{3}3^{m} + β_{1}1^{m} = s2^{m}.

If β_{4} = 0, then we have β_{3}3^{m} + β_{1}1^{m} = s2^{m}, but from Lemma 8 this implies s ≥ l_{3}, a contradiction our assumption that s < l_{3}. So now we have

α_{4}4^{m} + α_{3}3^{m} + α_{2}2^{m} + α_{1}1^{m} = 4^{m} + β_{3}3^{m} + β_{1}1^{m} = s2^{m}.

If α_{4} = 1, then by subtracting 4^{m} from the first two sums in the equation above, we obtain α_{2}2^{m} = (β_{3} − α_{3})3^{m} + (β_{1} − α_{1})1^{m}. But from Lemma 8 we have α_{2} ≥ l_{3}, a contradiction. So α_{4} = 0. So now we have

α_{3}3^{m} + α_{2}2^{m} + α_{1}1^{m} = 4^{m} + β_{3}3^{m} + β_{1}1^{m} = s2^{m}.

Finally, from α_{3}3^{m} + α_{2}2^{m} + α_{1}1^{m} = s2^{m} subtract α_{2}2^{m} from each side to obtain α_{3}3^{m} + α_{1}1^{m} = (s − α_{2})2^{m}. From Lemma 8 we obtain s − α_{2} ≥ l_{3} a clear contradiction to our assumption that s < l_{3}.

So we have shown that s ≥ l_{3}. Equation (6) then proves that in this case s = S(m, 3) = l_{3} and hence the seed value V (m, 3) = l_{3}2^{m}.

Case 4. 2l_{3} is the second smallest value. This assumption implies 2l_{3} ≤ l_{4}. Consider the following equation:

\begin{matrix}\underbrace{3^{m} + ⋯ + 3^{m}}_{(2^{m}−1)/d)} + \underbrace{1^{m} + ⋯ + 1^{m}}_{(3^{m}−2^{m})/d)} + \underbrace{3^{m} + ⋯ + 3^{m}}_{(2^{m}−1)/d)} + \underbrace{1^{m} + ⋯ + 1^{m}}_{(3^{m}−2^{m})/d)} \\ = \underbrace{3^{m} + ⋯ + 3^{m}}_{(2^{m}−1)/d)} + \underbrace{1^{m} + ⋯ + 1^{m}}_{(3^{m}−2^{m})/d)} + \underbrace{2^{m} + ⋯ + 2^{m}}_{l_{3}} = \underbrace{2^{m} + ⋯ + 2^{m}}_{2l_{3}} . \end{matrix}  (7)

From this we see s = S(m, 3) ≤ 2l_{3}. Assume that s = S(m, 3) < 2l_{3}. Since s < l_{4} (as in the proof of Case 2) we have α_{4} = β_{4} = 0. So we have

α_{3}3^{m} + α_{2}2^{m} + α_{1}1^{m} = β_{3}3^{m} + β_{1}1^{m} = s2^{m}.  (8)

Subtracting α_{3}3^{m} and α_{1}1^{m} from the first two sums yields

α_{2}2^{m} = (β_{3} − α_{3})3^{m} + (β_{1} − α_{1})1^{m}

and so by Lemma 8 we have α_{2} ≥ l_{3}. Also, subtracting α_{2}2^{m} from the first and third sums in Equation (8) we have

α_{3}3^{m} + α_{1}1^{m} = (s − α_{2})2^{m}.

So, again by Lemma 8 we get s − α_{2} = α_{1} + α_{3} ≥ l_{3}. Thus s = α_{1} + α_{2} + α_{3} ≥ 2l_{3} a contradiction to our assumption that s ≤ 2l_{3}.

So in this case s ≥ 2l_{3}. Equation (7) then proves that s = S(m, 3) = 2l_{3} and hence the seed value V (m, 3) = l_{4}2^{m}.

As was done after the proof of Theorem 9 we wish to compute the exact value of S(m, 3) using the results of Theorem 12.

We found that for every 1 ≤ m ≤ 200, 000 with m ≠ 1, 2, 4, 6, 12, 36, that S(m, 3) = 2l_{4} and hence V (m, 3) = 2l_{4}2^{m}.

This is Case 1 above. This calculation shows 2l_{4} ≤ l_{3} for all powers 36 < m ≤ 200, 000. Again we do not conjecture that 2l_{4} ≤ l_{3} for all m > 36, but certainly the evidence is very strong.

When m = 4 we are in Case 2, so l_{3} ≤ l_{4} ≤ 2l_{3} and hence S(4, 3) = l_{4} = 2^{4} + 1. We should note that m = 1 also has the property l_{3} ≤ l_{4} ≤ 2l_{3}, and although it doesn’t follow from the general proof, it is indeed true that S(1, 3) = l_{4} = 3 and so V (1, 3) = 3 × 2^{1} = 6, since 6 = 1 + 2 + 3 = 4 + 1 + 1 = 2 + 2 + 2.

When m = 6 we are in Case 3 so l_{4} ≤ l_{3} ≤ 2l_{4}, and hence S(6, 3) = l_{3} = 104.

Also note m = 2 also has the property that l_{4} ≤ l_{3} ≤ 2l_{4}, and indeed S(2, 3) = l_{3} = 8 and so V (1, 3) = 8×2^{2} = 32, since 32 = 4^{2}+2^{2}+2^{2}+2^{2}+1+1+1+1 = 3^{2}+3^{2}+3^{2}+1+1+1+1+1 = 2^{2} + 2^{2} + 2^{2} + 2^{2} + 2^{2} + 2^{2} + 2^{2} + 2^{2}. As a bonus here we see that 32 = 5^{2} + 7 × 1^{2} and hence four different sums of 8 squares are equal to 32. So we get S(2, 4) = 8 and hence T (8, 2, 4) = T (8, 2, 3) = 32.

Finally when m = 12 or m = 36, we have 2l_{3} < l_{4} and thus both these values fall into Case 4.

5 More than 3 ways

In this section we present a general theorem and a conjecture about seeds. Again let d = gcd(3^{m} − 2^{m}, 2^{m} − 1), l_{3} = \frac{3^{m}−1}{d} and l_{4} = 2^{m} + 1. Also let the sums

S_{3} = \underbrace{3^{m} + ⋯ + 3^{m}}_{\frac{2^{m}−1}{d}} + \underbrace{1 + ⋯ + 1}_{\frac{3^{m}−2^{m}}{d}} and S_{4} = 4^{m} + \underbrace{1 + ⋯ + 1}_{2^{m}} .

Theorem 15. Given t, there exists a number m_{0}, such that if m ≥ m_{0}, then the seed number S(m, t) is bounded above by the t − 1st smallest of the values al_{3} + bl_{4} over all a, b ≥ 0. The seed value V (m, 3) = S(m, 3) × 2^{m}.

Proof. Let n = min(l_{3}, l_{4}) and let m_{0} = max{m | 5^{m} < (t − 1)n2^{m}}. Let n_{0} be the t − 1st smallest of the values al_{3} + bl_{4} over all a, b ≥ 0. Finally define the sum aS_{3} + bS_{4} + \overline{2^{m}} to be a copies of S_{3} added to b copies of S_{4} added to n_{0} − (al_{3} + bl_{4}) copies of 2^{m}. Now it is clear that for all al_{3} + bl_{4} ≤ n_{0}, the sum aS_{3} + bS_{4} + \overline{2^{m}} = n_{0}2^{m}. But also, if m ≥ m_{0}, then k^{m} ≥ (t − 1)n2^{m} ≥ n_{0}2^{m} for all k ≥ 5 and hence no sum with n_{0} terms and equal to n_{0}2^{m} can contain any k^{m} for k ≥ 5. Thus the t − 1 sums aS_{3} + bS_{4} + \overline{2^{m}} with the sum of m_{0} 2^{m}’s are all equal, proving our upper bound.

Note that in the proof of the previous theorem in order to obtain the upper bound it was not necessary to prove that no sum could contain a k^{m} for any k ≥ 5. We included that fact in order to add credence to our conjecture below.

Indeed, we believe that the number presented in Theorem 15 is the actual seed number. We state this in the following conjecture. One can see that both Theorem 9 and Theorem 12 follow from this conjecture.

Conjecture 16. Given t, there exists a number m_{0}, such that if m ≥ m_{0}, then the t − 1st smallest of the values al_{3} + bl_{4} over all a, b ≥ 0 is the seed number S(m, t) and the seed value V (m, 3) = S(m, 3) × 2^{m}.

6 Conclusion

The generalized taxicab number T (n, m, t) is equal to the smallest number that is the sum of n m^{th} powers in t ways. This definition is inspired by Ramanujan’s observation that 1729 = 1^{3} + 12^{3} = 9^{3} + 10^{3} is the smallest number that is the sum of two cubes in two ways and thus 1729 = T (2, 3, 2). In this paper we first proved that for any given positive integers m and t, there exist a seed for the generalized taxicab number, i.e., there exists a number s = S(m, t) such T (s + k, m, t) = T (s, m, t) + k for every k ≥ 0. We then found explicit expressions for this seed number when the number of ways t is 2 or 3. We ended with a general theorem and conjecture about the seed number S(m, t) for all t.

Addendum: Research for this paper was mostly undertaken while the authors were together in their first year of graduate school in mathematics at The Ohio State University in 1974. This paper should have appeared shortly after that, but at least it is finally finished now. (It only took another 45 years).

References

[1] Christian Boyer, New upper bounds for taxicab and cabtaxi numbers, J. Integer Sequences 11 (2008), Article 08.1.6.

[2] Christian Boyer, New upper bounds for taxicab and cabtaxi numbers, http://www.

   christianboyer.com/taxicab/.

[3] Avery Carr, Ramanujan’s taxicab number, https://blogs.ams.org/mathgradblog/

   2013/08/15/ramanujans-taxicab-number/ .

[4] G. H. Hardy, P. V. Seshu Aiyar, and B. M. Wilson, Collected Papers of Srinivasa Ramanujan, Cambridge University Press, 1927. Reprinted by Chelsea, 1962.

[5] Jean-Charles Meyrignac, Computing minimal equal sums of like powers, http://euler.

   free.fr.

[6] Ivars Peterson, Taxicab numbers, Science News Online, 2002. Available at https://www.

   sciencenews.org/article/taxicab-numbers.

[7] Joseph H. Silverman, Taxicabs and sums of two cubes, Amer. Math. Monthly 100 (1993), 331–340.

2010 Mathematics Subject Classification: Primary 11A67; Secondary 11L99. Keywords: taxicab number, Ramanujan.

(Concerned with sequence \underline{A011541}.)

Received January 25 2019; revised versions received May 3 2019; May 6 2019. Published in Journal of Integer Sequences, May 17 2019.

Return to Journal of Integer Sequences home page.