Continuing on with the Project Euler solutions I'm now going to look at the second problem:


Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million.


Back when I studied math (B.Sc. Math, UBC 1980) the definition of the Fibonacci sequence was usually given as something like:

The sequence defined by this recurrence relation is:

1, 1, 2, 3, 5, 8, 13, 21, ...

For the purposes of this problem the series is defined a bit differently:

So that the sequence is:

1, 2, 3, 5, 8, 13, 21, 34, ...

If I used the first definition my answer would be off by one. There are a lot of ways to implement this in F#. After briefly flirting with a matrix multiplication formula (in a foolish attempt to avoid recursion) I came up with this:

let fib m n =
    let rec inner a b =
        seq {
            let c = a + b
            yield c
            yield! inner b c
        }
    seq {
        yield m
        yield n
        yield! inner m n
    }

For the purposes of this sequence the two parameters of the function are the first two values in the series. I coded it this way so that type inference would allow it to be used with any integer type. This is definitely not the simplest F# implementation of the Fibonacci series. A naive implementation might look like this:

let rec fib_naive n =
    match n with
    | 1|2 -> n
    | k -> fib_naive (k-1) + fib_naive (k-2)

The problem with this code is that in the computation of the n-1^th element requires the computation of the n-2^nd element. But then you turn around and recompute the  n-2^nd element all over again. In other words you do the same computation twice which, for large values of n, is just wasteful. Also, to use this function you would need to know the approximate value of n for which fib_naive n is greater than 4 million.

The part I like about the first function is that at each step you already have the previous value of the series computed and you can just use it. Plus the first function is really a generator. You can get the next element from it as many times as you want (or as is allowed by the underlying representation of an integer).

So, given the Fibonacci number generator, the solution to this problem can be written as:

fib 1 2 |> 
    Seq.takeWhile (fun n -> n < 4000000) |> 
    Seq.filter (fun n -> n%2 = 0) |> 
    Seq.sum |> 
    printfn "sum = %A"

To put it in words, take the Fibonacci series and select the values from it that are less than 4 million. Then select all the even numbers in the new subset and add them together.