reaktor42 - a personal platform

Project Euler: Problem 2

The second post in a series about solving Project Euler problems using Haskell.

Problem 2

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Solution

The basic steps we have to take

Transformed from prose to Haskell it should look like the following where fibs is assumed to be the infinite Fibonacci sequence.

euler002 :: Int
euler002 = sum $ filter odd $ takeWhile (< 4000001) $ fibs

It’s compelling to translate the recursive definition of the Fibonacci sequence directly into Haskell since its so trivial.

fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

fibs :: [Int]
fibs = map fib [0..]

But its horribly inefficient since we call fib repetitively with the same parameter over and over again.

We could use memoization to save us from recalculating the same expression over and over again. Let’s try that by storing all calculated numbers in a list and use this list as a lookup table.

memo_fib :: Int -> Int
memo_fib = (map fib [0..] !!)
  where
    fib 0 = 0
    fib 1 = 1
    fib n = memo_fib (n - 1) + memo_fib (n - 2)

fibs' :: [Int]
fibs' = map memo_fib [0..]

Normally you would prefer a data structure with a \(O(1)\) lookup behavior but you get the idea.

A much neater way is to use Haskell’s laziness to compute the first \(n\) numbers with \(O(n)\) additions.

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Looks good, but we can optimize further if we dig deeper into the numbers.

\(0,1,1,2,3,5,8,13,21,34,55,89,144,...\)

If we replace all odd numbers with an \(O\) and all even numbers with an \(E\) we see a serial pattern.

\(E,O,O,E,O,O,E,O,O,E,O,O,E,...\)

We can use these information to create a function which generates a list featuring only the even numbers. We define a recursive function which takes the two odd numbers, creates the even number and calls itself again with the next two odd numbers.

For a better unterstanding lets rewrite the pattern \(O,O,E,O,O\) by assuming \(a\) as the first odd number and \(b\) as the second odd number.

\(a,b,a+b,a+2b,2a+3b\)

That’s all we need to know to define a function which uses this pattern and generates a list covering only the even numbers.

evenFibs = evenFibs' 1 1
  where
    evenFibs' a b = (a + b) : evenFibs' (a + 2*b) (2*a + 3*b)

Finally we just sum up all numbers less then or equal to 4000000 and we are done.

euler002' :: Int
euler002' = sum $ takeWhile (< 4000001) $ evenFibs' 1 1
  where
    evenFibs' a b = (a + b) : evenFibs' (a + 2*b) (2*a + 3*b)