Posts Tagged ‘taxicab’

Programming Praxis – Taxicab Numbers

November 9, 2012

In today’s Programming Praxis exercise, our goal is to prove that 1729 is the smallest number that can be written as the sum of two cubes. Let’s get started, shall we?

A quick import:

import Text.Printf

To find the pairs of cubes we use an incremental search algorithm that covers al of the unique combinations.

cubesums :: Integer -> [(Integer, Integer)]
cubesums n = f 0 (round $ fromIntegral n ** (1/3)) where
    f x y = if y < x then [] else case compare (x^3 + y^3) n of
                EQ -> (x,y) : f (x + 1) (y - 1)
                LT -> f (x + 1) y
                GT -> f x (y - 1)

Once we have a way of determining the cube sums, generating the taxi cab numbers is trivial. By using a pattern match to get the cube sums we don’t have to specify that there must be two solutions as a separate condition.

taxicab :: [(Integer, (Integer, Integer), (Integer, Integer))]
taxicab = [(n,p,q) | n <- [1..99999], [p,q] <- [cubesums n]]

And finally we pretty-print the result.

main :: IO ()
main = mapM_ (\(n,p,q) -> printf "%d : %s %s\n" n (show p) (show q)) taxicab