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) Console.ReadLine()
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) Console.ReadLine()
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.
