Spoilers! Project Euler solutions in Haskell

Not having done any Haskell programming in ages, I was provoked by Louis Sterrett to try some of the Euler Project problems. Even simple programs are good & healthy exercise, excellent for driving off the spleen and regulating the circulation. Besides, I’m still not very au fait with standard Haskell style and idioms, so it’s interesting to compare my solutions with others’ – the Haskell wiki also has some suggested solutions.

Here are my solutions to problems 1-2 and 4-5  (my solution to problem 3 was a little too disgusting even for my plebeian tastes; the ones on the Haskell wiki are much better). Don’t read ahead if you want to try the problems yourself!

1. Find the sum of all the multiples of 3 or 5 below 1000.

Solution 1 – brute force:

```problem1 = sum \$ nub \$ filter (`isMultipleOf` [3,5]) [1..999]
where
isMultipleOf n factors = (filter (\f -> n `mod` f == 0) factors) /= []
```

“nub” filters out duplicates from a list – why it’s not called something like “unique”, I don’t know.

Solution 2 – formula for summing the series:

```-- calculate sum of multiples of n, up to limit
sumToLimit f limit = f * (upper) * (upper + 1) `div` 2
where
upper = (limit-1) `div` f

problem1' =
(sumToLimit 3 limit) + (sumToLimit 5 limit) - (sumToLimit 15 limit)
```
2. Find the sum of even-valued terms in the Fibonacci sequence whose values do not exceed four million.

Solution 1 – brute force:

```fibNums = 1 : 2 : (generateFibs 1 2)
where
generateFibs n1 n2  =
let next = n1 + n2
in next : (generateFibs n2 next)

problem2 = sum \$ filter even \$ takeWhile (< 4000000) fibNums
```

Solution 2 – Binet’s formula for terms of the sequence (see Wikipedia).

```fib n = floor \$ ((a ** n) / (5 ** 0.5)) + 0.5
where
a = (1 + (5 ** 0.5)) / 2

problem2' = sum \$ filter even \$ takeWhile (< 4000000) \$ tail \$ map fib [1..]
```

(The Project Euler page defines the Fibonacci sequence as starting “1, 2, 3 …” rather than “1, 1, 2, 3 …”, so the “tail” function is used to discard the initial, unnecessary “1”.)

1. Find the largest palindrome made from the product of two 3-digit numbers.

Solution:

```import Data.List (sort)

isPalindrome xs = xs == (reverse xs)
isPalindromicNum = isPalindrome . show

problem4 = last \$ sort \$ palindromes
where
threeDigitNums = [999, 998 .. 100]
palindromes =
[i * j | i <- threeDigitNums, j <- threeDigitNums, isPalindromicNum (i*j)]
```
2. What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Solution:

```problem5 = foldr lcm 1 [1..20]
```

(This is almost cheating, really, because Haskell has a “lowest common multiple” function built in.)