= Ramanujan's Taxi Cab Numbers : A Solution =

<<TableOfContents>>

Here's one solution to the Taxi Cab function:

{{{
      ∇R←TaxiCab N;⎕IO;vals;sumCubes;cubes
[1]   ⎕IO←1
[2]   vals←⍳N
[3]   sumCubes←(vals∘.<vals)×cubes∘.+cubes←vals*3
[4]   R←(R=1⌽R)/R←R[⍋R←(,sumCubes)~0]
[5]   R←⍉R,[0.5](,¨(R⍷¨⊂sumCubes)×⊂vals∘.,vals)~¨⊂⊂0 0
      ∇ 
}}}

For example:
{{{
      TaxiCab 30
  1729  1 12  9 10
  4104  2 16  9 15
 13832  2 24  18 20
 20683  10 27  19 24
}}}

The output shows the taxi cab number followed by the pairs of terms. For example 1729 = 1^3^ + 12^3^ = 9^3^ + 10^3^

= An explanation of the APL code =

Let's explore the solution line by line. Lines [1] and [2] are easy enough : vals is assigned a vector of numbers, e.g.
{{{
      vals←⍳13
      vals
1 2 3 4 5 6 7 8 9 10 11 12 13
}}}

Now we want to compute the cubes of those values:
{{{
      cubes←vals*3
      cubes
1 8 27 64 125 216 343 512 729 1000 1331 1728 2197
}}}

The next step is to compute the sums of all the possible pairs of cubes:
{{{
      cubes∘.+cubes←vals*3
   2    9   28   65  126  217  344  513  730 1001 1332 1729 2198
   9   16   35   72  133  224  351  520  737 1008 1339 1736 2205
  28   35   54   91  152  243  370  539  756 1027 1358 1755 2224
  65   72   91  128  189  280  407  576  793 1064 1395 1792 2261
 126  133  152  189  250  341  468  637  854 1125 1456 1853 2322
 217  224  243  280  341  432  559  728  945 1216 1547 1944 2413
 344  351  370  407  468  559  686  855 1072 1343 1674 2071 2540
 513  520  539  576  637  728  855 1024 1241 1512 1843 2240 2709
 730  737  756  793  854  945 1072 1241 1458 1729 2060 2457 2926
1001 1008 1027 1064 1125 1216 1343 1512 1729 2000 2331 2728 3197
1332 1339 1358 1395 1456 1547 1674 1843 2060 2331 2662 3059 3528
1729 1736 1755 1792 1853 1944 2071 2240 2457 2728 3059 3456 3925
2198 2205 2224 2261 2322 2413 2540 2709 2926 3197 3528 3925 4394
}}}

However, we're only interested in pairs of cubes where the two numbers are different, and we don't want to consider both '3 and 4' and '4 and 3'. The expression {{{vals∘.<vals}}} gives an array in which there is a '1' in every position where the column number is greater than the row number:
{{{
      vals∘.<vals
0 1 1 1 1 1 1 1 1 1 1 1 1
0 0 1 1 1 1 1 1 1 1 1 1 1
0 0 0 1 1 1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1 1 1 1 1 1
0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 1 1 1 1 1 1 1
0 0 0 0 0 0 0 1 1 1 1 1 1
0 0 0 0 0 0 0 0 1 1 1 1 1
0 0 0 0 0 0 0 0 0 1 1 1 1
0 0 0 0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0
}}}

So Line [3] find the sums of pairs of cubes as follows:
{{{
      sumCubes←(vals∘.<vals)×cubes∘.+cubes←vals*3
      sumCubes
0 9 28 65 126 217 344 513  730 1001 1332 1729 2198
0 0 35 72 133 224 351 520  737 1008 1339 1736 2205
0 0  0 91 152 243 370 539  756 1027 1358 1755 2224
0 0  0  0 189 280 407 576  793 1064 1395 1792 2261
0 0  0  0   0 341 468 637  854 1125 1456 1853 2322
0 0  0  0   0   0 559 728  945 1216 1547 1944 2413
0 0  0  0   0   0   0 855 1072 1343 1674 2071 2540
0 0  0  0   0   0   0   0 1241 1512 1843 2240 2709
0 0  0  0   0   0   0   0    0 1729 2060 2457 2926
0 0  0  0   0   0   0   0    0    0 2331 2728 3197
0 0  0  0   0   0   0   0    0    0    0 3059 3528
0 0  0  0   0   0   0   0    0    0    0    0 3925
0 0  0  0   0   0   0   0    0    0    0    0    0
}}}

Line [4] is concerned with finding the taxi cab numbers themselves. First we convert the array of sums of cubes into a simple list and remove any 0s:
{{{
      R←(,sumCubes)~0
      R
9 28 65 126 217 344 513 730 1001 1332 1729 2198 35 72 ...etc
}}}
Now we sort the list into ascending order:
{{{
      R←R[⍋R←(,sumCubes)~0]
      R
9 28 35 65 72 91 126 133 152 189 217 224 243 ...etc 
}}}
Now we want to find duplicates in the list. These are the taxi cab numbers, since they can be expressed as the sum of two cubes in two different ways. The expression {{{R=1⌽R}}} produces a boolean vector with a '1' for every item in the list which is repeated, and we can use it with {{{/}}} to get the actual item values:
{{{
      R←(R=1⌽R)/R←R[⍋R←(,sumCubes)~0]
      R
1729
}}}

Line [5] is concerned with finding which pairs of values produced each taxi cab number. First we find each taxi cab number in the sum-of-cubes array. Let's consider the simple case first, where we found only one taxi cab number:
{{{
      R
1729
      R⍷sumCubes
0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
}}}
You can see that it was found at row 1, column 12 and also at row 9, column 10. In other words, 1729 = 1^3^ + 12^3^ = 9^3^ + 10^3^.

How do we find out the row/column numbers of the two '1's ? The following expression gives all the pairs of row and column values:
{{{
     vals∘.,vals
 1 1   1 2   1 3   1 4   1 5   1 6   1 7   1 8   1 9   1 10   1 11   1 12   1 13
 2 1   2 2   2 3   2 4   2 5   2 6   2 7   2 8   2 9   2 10   2 11   2 12   2 13
 3 1   3 2   3 3   3 4   3 5   3 6   3 7   3 8   3 9   3 10   3 11   3 12   3 13
 4 1   4 2   4 3   4 4   4 5   4 6   4 7   4 8   4 9   4 10   4 11   4 12   4 13
 5 1   5 2   5 3   5 4   5 5   5 6   5 7   5 8   5 9   5 10   5 11   5 12   5 13
 6 1   6 2   6 3   6 4   6 5   6 6   6 7   6 8   6 9   6 10   6 11   6 12   6 13
 7 1   7 2   7 3   7 4   7 5   7 6   7 7   7 8   7 9   7 10   7 11   7 12   7 13
 8 1   8 2   8 3   8 4   8 5   8 6   8 7   8 8   8 9   8 10   8 11   8 12   8 13
 9 1   9 2   9 3   9 4   9 5   9 6   9 7   9 8   9 9   9 10   9 11   9 12   9 13
 10 1  10 2  10 3  10 4  10 5  10 6  10 7  10 8  10 9  10 10  10 11  10 12  10 13
 11 1  11 2  11 3  11 4  11 5  11 6  11 7  11 8  11 9  11 10  11 11  11 12  11 13
 12 1  12 2  12 3  12 4  12 5  12 6  12 7  12 8  12 9  12 10  12 11  12 12  12 13
 13 1  13 2  13 3  13 4  13 5  13 6  13 7  13 8  13 9  13 10  13 11  13 12  13 13
}}}

So we can find the answer as follows:
{{{
     (R⍷sumCubes)×vals∘.,vals
 0 0  0 0  0 0  0 0  0 0  0 0  0 0  0 0  0 0  0 0   0 0  1 12  0 0
 0 0  0 0  0 0  0 0  0 0  0 0  0 0  0 0  0 0  0 0   0 0  0 0   0 0
 0 0  0 0  0 0  0 0  0 0  0 0  0 0  0 0  0 0  0 0   0 0  0 0   0 0
 0 0  0 0  0 0  0 0  0 0  0 0  0 0  0 0  0 0  0 0   0 0  0 0   0 0
 0 0  0 0  0 0  0 0  0 0  0 0  0 0  0 0  0 0  0 0   0 0  0 0   0 0
 0 0  0 0  0 0  0 0  0 0  0 0  0 0  0 0  0 0  0 0   0 0  0 0   0 0
 0 0  0 0  0 0  0 0  0 0  0 0  0 0  0 0  0 0  0 0   0 0  0 0   0 0
 0 0  0 0  0 0  0 0  0 0  0 0  0 0  0 0  0 0  0 0   0 0  0 0   0 0
 0 0  0 0  0 0  0 0  0 0  0 0  0 0  0 0  0 0  9 10  0 0  0 0   0 0
 0 0  0 0  0 0  0 0  0 0  0 0  0 0  0 0  0 0  0 0   0 0  0 0   0 0
 0 0  0 0  0 0  0 0  0 0  0 0  0 0  0 0  0 0  0 0   0 0  0 0   0 0
 0 0  0 0  0 0  0 0  0 0  0 0  0 0  0 0  0 0  0 0   0 0  0 0   0 0
 0 0  0 0  0 0  0 0  0 0  0 0  0 0  0 0  0 0  0 0   0 0  0 0   0 0
      (,(R⍷sumCubes)×vals∘.,vals)~⊂0 0
 1 12  9 10
}}}

We now need to take care of the fact that there might be more than one taxi-cab number, so the expression becomes:
{{{
      (,¨(R⍷¨⊂sumCubes)×⊂vals∘.,vals)~¨⊂⊂0 0
  1 12  9 10
}}}

Finally, we create an array with the first row containing the taxi cab numbers and the second row containing the terms, flip it using {{{⍉}}} to make the result more readable, and we're done.
 
= Other investigations concerning 1729 =

We can define a handy function to break a number up into its digits:

{{{
      ∇R←base Digits val
[1]  ⍝ Returns individual digits of 'val' when expressed in base 'base',
[2]  ⍝ e.g. 10 Digits 1729 gives 1 7 2 9
[3]   R←((1+⌊base⍟val+0=val)⍴base)⊤val
      ∇   
}}}

(a) Now to find out which numbers are evenly divisible by the sum of their digits. Here's a test of the range 1720-1770
{{{
      (0=(+/¨10 Digits¨ X)|X)/X←1719+⍳50 
1725 1728 1729 1740 1744 1746 1764 1770
}}}

(b) Now we investigate which of the first 100000 numbers behave in the same way as 1729, i.e. 
        1 + 7 + 2 + 9 = 19&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;;&nbsp;&nbsp;&nbsp;&nbsp;19 × 91 = 1729  
{{{
      (vals=sums×10⊥¨⌽¨10 Digits¨sums←+/¨10 Digits¨ vals)/vals←⍳100000
1 81 1458 1729
}}}

In fact these are the only four natural numbers which have this property.

<< [[TaxiCabNumbers/Task|The task]]

&nbsp;
&nbsp;

Author: SimonMarsden