Geeks With Blogs

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

Console.WriteLine(res)

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

Console.WriteLine(res)

We could of course condense the code but I think this best illustrates the individual steps. No doubt there are even more concise approaches to solving this solution in F# and I look forward to any comments identifying other more elegant approaches as my knowledge of the various available functions is still limited.

Related Posts on Geeks With Blogs Matching Categories

Comments on this post: F# Project Euler Problem 2

# re: F# Project Euler Problem 2 Ok what do you guys think of this ? I found that Seq can be made lazy using unfold ... (I copied the fibonacci sequence from another website while trying to figure this out)

let lazyFib =
Seq.unfold
(fun (current, next) -> Some(current, (next, current + next)))
(0, 1)

let euler2 =
lazyFib
|> Seq.filter (fun x -> x % 2 = 0)
|> Seq.takeWhile (fun x -> x < 4000000)
|> Seq.sum

Cheers,

Danny
Left by Danny on Jun 21, 2010 12:16 PM