Euler Problem 95 – Recursion

After I got this one, I went to the Euler Project problem thread and wanted to read up on what other Haskellers had done. I found lots of posted Haskell routines that make the solution overly complicated, and look like spaghetti. My solution is made of nice and pretty code.

This problem I stared at for a long time. Its not a very difficult problem, but it can really only be solved recursively using native Haskell code. I will not use any mutable arrays. So this is really my first recursive routine. Admittedly, I ball-parked the upper limit to 15K, and got the answers on the first try. This routine runs on an old PC in under a minute.

sumdiv :: Integer -> Integer
sumdiv n = sum $ 1 : filter ((== 0) . rem n) [2 .. n `div` 2]

build :: [Integer] -> [Integer]
build chain
	| (last chain) == 1 = []
	| (last chain) > 1000000 = []
	| (last chain) `elem` (init chain) = chain
	| otherwise = build (chain ++ [sumdiv (last chain)])

main = print $ snd $ maximum [(length c, minimum c) | n<-[12496..15000], let c=build [n], c /= []]

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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