APL Wiki
Ramanujan's Taxi Cab Numbers : A Solution
Contents
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 = 13 + 123 = 93 + 103
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 13Now 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 2197The 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 0Line [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 ...etcNow 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
1729Line [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 0You can see that it was found at row 1, column 12 and also at row 9, column 10. In other words, 1729 = 13 + 123 = 93 + 103.
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 10We 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 ; 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.
<< The task
Author: SimonMarsden