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

### Like this:

Like Loading...

*Related*

Tags: bonsai, code, Haskell, kata, numbers, praxis, programming, taxicab

This entry was posted on November 9, 2012 at 10:58 am and is filed under Programming Praxis. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply