 Today I thought I would give a bash at problem 2 of Euler.

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, …

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

My Solution (Brute Force)

So first of all I needed a Fibonacci generator. I resorted to one that recursively defines the Fibonacci number based on the index with a recursive call.

let rec Fib n = if n < 2 then 1 else Fib (n-2) + Fib(n-1) I then needed a function to say whether a number was even or not… using the modulus operator this was simple..

let isEven x = if x % 2 = 0 then true
else false

Finally I needed to generate a sequence of Fibonacci numbers within that did not exceed four million. I don’t know what index is the last even Fibonacci number so this presented a problem. Luckily I had bumped into lazy sequences before so decided to generate an sequence that only generated the next number on request. I have worked with the Seq.unfold method before but decided to try the Seq.initInfinite instead. This resulted in code that looked as follows…

let FibEvenApproach1 = Seq.initInfinite (fun index -> if isEven(Fib index) then Fib index else 0) All I needed to do now was tie it all up…

let res = FibEvenApproach1 |> Seq.takeWhile (fun n -> n < 4000000)
|> Seq.sum

My end complete solution looked like this…

open System

let rec Fib n = if n < 2 then 1 else Fib (n-2) + Fib(n-1)

let isEven x = if x % 2 = 0 then true
else false

let FibEvenApproach1 = Seq.initInfinite (fun index -> if isEven(Fib index) then Fib index else 0)

let res = FibEvenApproach1 |> Seq.takeWhile (fun n -> n < 4000000)
|> Seq.sum

A Better Way

While my solution generates the correct result, it is doing several unnecessary calculations… For instance it is calculating the Fibonacci for odd numbers which has unnecessary overhead.

If we examine the Fibonacci sequence again we can see a pattern…

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

O E O O E O O E O O E

Where the second, fifth, seventh number are even and this pattern continues throughout the sequence. Knowing this we can adjust our generator to only calculate even numbers…

let FibEvenApproach2 = Seq.initInfinite (fun index -> Fib((index*3)-1)) By replacing FibEvenApproach1 with FibEvenApproach2 we get an optimized solution that looks as follows…

open System

let rec Fib n = if n < 2 then 1 else Fib (n-2) + Fib(n-1)

let FibEvenApproach2 = Seq.initInfinite (fun index -> Fib((index*3)-1))

let res = FibEvenApproach2 |> Seq.takeWhile (fun n -> n < 4000000)
|> Seq.sum