Skip to main content
2 of 2
Added additional material
Joe Silverman
  • 47.4k
  • 2
  • 149
  • 241

There are a few issues here.

(1) It is relatively easy to show that Ta($n$) exists, for example by using a point of infinite order on an elliptic curve $x^3+y^3=mz^3$ to show that there is at least one number with $n$ distinct representations. However, the number tends to be divisible by a large cube, or alternatively, the $(x,y)$ pairs tend to have large $\gcd(x,y)$.

(2) So let's define $\operatorname{Ta}^*(n)$ to be the smallest that can be expressed as a sum of two relatively prime positive integer cubes in $n$ different distinct ways. Then $\operatorname{Ta}^*(2)=1729$,$\operatorname{Ta}^*(3)=15170835645$ (Vojta), $\operatorname{Ta}^*(4)=1801049058342701083$ (Gascoigne, Moore, independently), and there is some reason to believe that $\operatorname{Ta}^*(5)$ doesn't exist. (Or in any case, at some point $\operatorname{Ta}^*(n)$ doesn't exist.)

(3) To get back to your question, the size of $\operatorname{Ta}(n)$ probably (maybe?) grows exponentially with $n$. And increased computer power, even with Moore's law, has a hard time keeping up with a problem whose computational complexity grows exponentially. So for example, if increasing from $n$ to $n+1$ makes the taxicab search space grow by a factor of 100, and if it took 2 years of computer time to find $T(n)$, it's going to require a much faster computer to compute $T(n+1)$.


It looks as if $\operatorname{Ta}(n)$ may be growing superexponentially in $n$, although of course there isn't a lot of data, and the values for $7\le n\le 12$ are upper bounds. But the last line of this table is suggestive. \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline n & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ \hline \dfrac{\log\operatorname{Ta}(n)}{n} &3.73 & 6.10 & 7.39 & 7.69 & 8.59 & 9.34 & 9.99 & 10.52 & 11.25 & 12.03 & 13.02 \\ \hline \dfrac{\log\operatorname{Ta}(n)}{n\ln(n)} & 5.38 & 5.55 & 5.33 & 4.78 & 4.79 & 4.80 & 4.80 & 4.79 & 4.89 & 5.02 & 5.24 \\ \hline \end{array}

Joe Silverman
  • 47.4k
  • 2
  • 149
  • 241