Programming Praxis – Taxicab Numbers

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

Tags: , , , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: