Title: Understand taxicab numbers in C#

First some background. Taxicab numbers are the smallest numbers that can be expressed as a sum of two positive cubes in n distinct ways. In other words, Taxicab(n) is the smallest number A where A = B³ + C³ for n different pairs of numbers B and C.

For example, Taxicab(2) = 1729 because it's the smallest number that is expressible as the sum of two cubes in two distinct ways (n = 2). Those ways are 1³ + 12³ and 9³ + 10³. Because there are two combinations, this is Taxicab(2).

For a bizarre story that explains why these numbers are called taxicab numbers, see this Wikipedia entry.

Anyway, I was watching "Futurama" reruns the other day and in the episode "Lesser of Two Evils" it comes out that Flexo's and Bender's serial numbers are 3370318 and 2716057 respectively. Bender also says that both are expressible as a sum of two cubes and they have a good laugh.

Naturally I had to write a program to find the cubes.

If A = B³ + C³, then either B³ or C³ must be no more than A/2. Assume B < C. Then B³ ≤ A/2, so B ≤ cuberoot(A/2). That means you can find the two numbers by looking at all of the cubes between 0 and cuberoot(A/2), subtracting that value from A, and seeing if the remainder is a perfect cube.

That's exactly the approach this example takes. When you enter a number and click the Go button, the program loops variable B from 0 to cuberoot(A/2). (In C# you can calculate the cube root of a number by raising it to the 1/3 power.)

For each possible value B, the code calculates A - B³ and takes the integer cube root to see what C would be. If C³ exactly equals A - B³, then we have a solution.

The program continues to check other values of B to see if there are other solutions. Here's the code.

private void btnGo_Click(object sender, EventArgs e) { txtResult.Clear(); this.Cursor = Cursors.WaitCursor; long A = long.Parse(txtNumber.Text); long max_B = (long)Math.Pow(A / 2.0, 1.0 / 3.0); if (2 * max_B * max_B * max_B < A) max_B++; // Try numbers up to the cube root of A. for (int B = 0; B <= max_B; B++) { long remainder = A - (B * B * B); long C = (long)Math.Round(Math.Pow(remainder, 1.0 / 3.0)); if (C * C * C == remainder) { txtResult.Text += B + "^3 + " + C + "^3 = " + (B * B * B) + " + " + (C * C * C) + "\r\n"; txtResult.Select(0, 0); Application.DoEvents(); } } System.Media.SystemSounds.Beep.Play(); this.Cursor = Cursors.Default; }

The program found that Flexo's serial number 3370318 = 119³ + 119³ = 1685159 + 1685159.

Much to my surprise (because Futurama's nerd humor is usually correct), Bender's serial number is not expressible as a sum of two positive cubes. However, it is 2716057 = (-951)³ + 952³ = -860085351 + 862801408. If you allow negative numbers it works, but it also it seems like anything might be possible if you allow negative numbers.

Notes:

• The smallest number expressible in N different ways as the sum of 2 positive cubes is called Taxicab(N).
• Taxicab(2) = 1729 is expressible as 1³ + 12³ and 9³ + 10³
• Taxicab(3) = 87539319
• Taxicab(4) = 6963472309248
• Taxicab(5) = 48988659276962496 (although this number is too big to fit in C#'s decimal data type)
• It is not known whether Taxicab(6) = 24153319581254312065344. That number is expressible in 6 ways as a sum of two cubes but it's not known whether that is the smallest such number. If you can write a program to check 1 billion numbers per second, then you can verify this in a bit under 766,000 years.

Download the example to experiment with it and to see additional details.