Ramanujan's Taxi, by Eric Anderson The problem is to find "Ramanujan's Taxi", the smallest number expressible as the sum of two cubes in two distinct ways. The most compact solution is four lines long: || generate cubes from a number and a list || gc :: num -> [num] -> [num] gc a (b:bs) = (a^3 + b^3) : gc a bs || generate cubes from a pair of lists || gen_cube_pairs :: [num] -> [num] -> [num] gcp (a:as) = (2*a^3) : merge (gc a as) (gcp as) || as above, this generates only distinct pairs || find duplicates by comparing successors dupes (a:b:as) = a : dupes (b:as), if a = b = dupes (b:as), otherwise fast_taxi = dupes (gcp [1..]) || Four lines! And fast! The full solution invokes various primitives relating to infinite lists, such as the distinct-pairs problem implicit in the above. And I volunteer to take up as much time on Wed (or Fri?) as you like. -- Eric A. ======================================= email: eric@cs.washington.edu Eric J. Anderson Department of Computer Science University of Washington 427 Sieg Hall Seattle, WA 98195 ======================================= The full text follows: |||||||||||||||||||||||||||||||||||||||||| || Problem 4: Ramanujan's Taxi || || The legendary Indian mathematician Ramanujan was known || for his extraordinary familiarity with the properties of the || natural numbers. The following famous anecdote is told || by Littlewood (a collaborator of Hardy, and himself no slouch): || || "I remember once going to see him when he was lying ill at || Putney. I had ridden in taxicab 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.'" || || Our task is to find Ramanujan's Taxi, i.e., the smallest positive || integer expressible in two distinct ways as the sum of two cubes || of positive integers. || || A procedural approach might tackle the problem as follows: || for n = 1 to infinity || loop through i, j <= n**(1/3), say || test i**3 + j**3 = n? || have we found two matches? || || The functional language approach is as follows: || make a list of all sums-of-pairs-of-cubes || see if the list has any duplicates || || The two approaches are much different! || || To solve this, we start by implementing some functions on infinite lists: || -- the list of all pairs from two infinite lists || -- the list of all distinct pairs (i.e., not including reversed order) || -- duplicates in an infinite list || Then, we successively improve.... || The answers are || slow_taxi || better_taxi || fast_taxi (four lines!) || nice_taxi || |||||||||||||||||||||||||||||||||||||||||| || || First, generate all pairs, using the canonical ordering (Hopcroft and Ullman's "pair generator") || gen_all_pairs :: [num] -> [num] -> [(num,num)] gen_all_pairs as [] = [] gen_all_pairs [] bs = [] gen_all_pairs (a:as) (b:bs) = (a,b) : merge_pairs (merge_pairs top middle) side where top = pair_up_1 a bs middle = gen_all_pairs as bs side = pair_up_2 as b pair_up_1 :: num -> [num] -> [(num,num)] pair_up_1 a (b:bs) = (a,b) : (pair_up_1 a bs) pair_up_2 :: [num] -> num -> [(num,num)] pair_up_2 (a:as) b = (a,b) : (pair_up_2 as b) merge_pairs :: [(num,num)] -> [(num,num)] -> [(num,num)] merge_pairs ((a,b):abs) ((x,y):xys) = (a,b) : merge_pairs abs ((x,y):xys), if (a+b) <= (x+y) = (x,y) : merge_pairs ((a,b):abs) xys, otherwise all_pairs = gen_all_pairs [1..] [1..] || || Now, generate all distinct pairs by a very simple modification: only top and middle || gen_all_distinct_pairs :: [num] -> [num] -> [(num,num)] gen_all_distinct_pairs as [] = [] gen_all_distinct_pairs [] bs = [] gen_all_distinct_pairs (a:as) (b:bs) = (a,b) : merge_pairs top middle where top = pair_up_1 a bs middle = gen_all_distinct_pairs as bs all_distinct_pairs = gen_all_distinct_pairs [1..] [1..] || || Now convert the list to cubes || cube_sum (x,y) = x^3 + y^3 all_distinct_cubes = map cube_sum all_distinct_pairs || || Now look for duplicates: || -- make all "completely distinct" pairs (= "cd_pairs") || meaning distinct pairs but not self-pairs || -- then any pair of identical numbers comes from a Ramanujan Taxi || || This sounds plausible but in practice is highly odiferous, for two reasons: || -- generating all "completely distinct" pairs is actually a bit tricky || -- looking for duplicates by constructing all possible pairs is VERY SLOW || || But we CAN make this work, with /heap = 1000000 and some patience (about three minutes, I guess) || || First, generate all "cd" pairs: || We make a small observation for efficiency: the 'gen_..._pairs' functions take as || arguments two lists that are always the same!, so define them instead as || taking a single argument (this might reduce demands on the heap) || Also, the following straightforward implementation doesn't work (nothing is ever || returned): || |||gen_all_cd_pairs (a:as) = merge_pairs top middle ||| where top = pair_up_1 a as ||| middle = gen_all_cd_pairs as ||| || Instead, make sure that at least one element comes out of the top-level call: gen_all_cd_pairs (a:b:as) = (a,b) : merge_pairs top middle where top = pair_up_1 a as middle = gen_all_cd_pairs (b:as) || Now, a duplicate is a pair from the cd_pairs list, whose first and second elements agree: slow_dup ((a,b):as) = a : slow_dup as, if a = b = slow_dup as, otherwise slow_taxi = slow_dup (gen_all_cd_pairs all_distinct_cubes) || This works but is SLOW. || Instead, let's look for duplicates by KEEPING THE LIST IN ORDER of size of cube. Then, || duplicates are always successive elements, and a single scan of the list will find them. || We need to go back and modify the merge function: merge_cube_pairs :: [(num,num)] -> [(num,num)] -> [(num,num)] merge_cube_pairs ((a,b):abs) ((x,y):xys) = (a,b) : merge_cube_pairs abs ((x,y):xys), if (a^3+b^3) <= (x^3+y^3) = (x,y) : merge_cube_pairs ((a,b):abs) xys, otherwise || || As before, generate all distinct pairs by examining only top and middle || (and using 'merge_cube_pairs') || gen_all_cube_pairs :: [num] -> [num] -> [(num,num)] gen_all_cube_pairs as [] = [] gen_all_cube_pairs [] bs = [] gen_all_cube_pairs (a:as) (b:bs) = (a,b) : merge_cube_pairs top middle where top = pair_up_1 a bs middle = gen_all_cube_pairs as bs all_cube_pairs_ordered = gen_all_cube_pairs [1..] [1..] all_distinct_cubes_ordered = map cube_sum all_cube_pairs_ordered faster_dup (a:b:as) = a : faster_dup (b:as), if a = b = faster_dup (b:as), otherwise better_taxi = faster_dup all_distinct_cubes_ordered || || That's better! No extra heap space needed. || || Finally, let's try to write the shortest possible code: || -- assume infinite lists (so [] cases are not necessary) || -- keep track only of the cubes themselves (not the pairs that give rise to it), || -- use the built-in 'merge', || -- apply the generate function only to "square" pairs of lists, || i.e., to two identical lists || -- and keep the list sorted by cube, so that duplicates are successive || generate cubes from a number and a list || gc :: num -> [num] -> [num] gc a (b:bs) = (a^3 + b^3) : gc a bs || generate cubes from a pair of lists || gen_cube_pairs :: [num] -> [num] -> [num] gcp (a:as) = (2*a^3) : merge (gc a as) (gcp as) || as above, this generates only distinct pairs || find duplicates by comparing successors dupes (a:b:as) = a : dupes (b:as), if a = b = dupes (b:as), otherwise fast_taxi = dupes (gcp [1..]) || Four lines! And fast! || For completeness, we should really return the components of the "taxi" numbers, || not just their totals. A simple modification to the better_taxi version will || do the trick, starting with all_cube_pairs_ordered. And for grins we'll dress up || the output: || verbose_dup ((a1,a2):(b1,b2):abs) = (taxi_output a1 a2 b1 b2): verbose_dup ((b1,b2):abs), if a1^3+a2^3=b1^3+b2^3 = verbose_dup ((b1,b2):abs), otherwise taxi_output a1 a2 b1 b2 = "Taxi!! " ++ sa1 ++ " cubed plus " ++ sa2 ++ " cubed equals " ++ b_sum where sa1 = shownum a1 sa2 = shownum a2 b_sum = sb1 ++ " cubed plus " ++ sb2 ++ " cubed equals " ++ ss || ++ "\n" sb1 = shownum b1 sb2 = shownum b2 ss = shownum (a1^3 + a2^3) || Printing a list of strings doesn't enable "\n"; but ... || ...happily, an infinite string is just an infinite list! print_taxi (a:as) = a ++ "\n" ++ (print_taxi as) nice_taxi = print_taxi (verbose_dup all_cube_pairs_ordered)