Project Euler Problem #2

Home/Uncategorized/Project Euler Problem #2

I’m beginning to learn F# and the best way for me to go about that is to start applying it. There are some interesting computational problems over at Project Euler . This post is the continuation of a series of posts each involving a separate Project Euler problem. This is my first solution to Project 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.

Here’s my first attempt at it:

open System
 
let fibonacci = Seq.unfold (fun (current, next) -> Some (current + next, (next, current + next))) (0, 1)
let isEven = (fun i -> i % 2 = 0)
 
let sumOfEvenFibonacciNumbers = Seq.sum (Seq.filter isEven (Seq.takeWhile (fun i -> i < 4000000) fibonacci))
 
printfn "Project Euler Problem #2: Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million."
printfn "Answer: %d" sumOfEvenFibonacciNumbers

Notice though that I have to use a lot of parenthesis due to composition – there’s gotta be a better way that is clearer and doesn’t involve so many parenthesis.

Leaving the fibonacci and isEven definitions alone:

[fsharp firstline="6"] let sumOfEvenFibonacciNumbers = fibonacci |> Seq.takeWhile (fun i -> i < 4000000) |> Seq.filter isEven |> Seq.sum

Now that's a lot nicer - it's much more obvious that we start off with the original Fibonacci sequence, stop at 4 million, take only the even ones, and finally sum them all up.

Now to fix a bug in our Fibonacci sequence. Typically the Fibonacci sequence starts with (0, 1) or (1, 1), not (1, 2) - but our problem statement specifies the start as (1, 2) (although even if the problem is evaluated starting at (0, 1) or (1, 1) the result is the same). The fibonacci definition above specifies (0, 1) as the starting point for the unfold operation...however the first two terms of the generated sequence are (1, 2). What's going on?

When we return the return the value we need to make sure to return the initial values. Here's the buggy line of code:

[fsharp firstline="3"] fun (current, next) -> Some (current + next, (next, current + next))

And the corrected version:

[fsharp firstline="3"] fun (current, next) -> Some (current, (next, current + next))

Leave a Comment