Project Euler — Problem 2 Solution

Problem

Each new term in the Fibonac­ci sequence is gen­er­at­ed by adding the pre­vi­ous two terms. By start­ing 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-val­ued terms in the sequence which do not exceed four mil­lion.

Solution

Here’s my solu­tion in F#:

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

let fibTotal =
    fibonacciSeq
    |> Seq.takeWhile (fun n -> n < 4000000)
    |> Seq.filter (fun n -> n % 2 = 0)
    |> Seq.sum

Here I’ve used a sequence, whilst a sequence is sim­i­lar to a list or array in F# in that it holds a series of ele­ments, there’s a cru­cial dif­fer­ence, each sequence ele­ment is com­put­ed only as required so it pro­vides bet­ter per­for­mance than a list in sit­u­a­tions which not all ele­ments are used. If that sounds famil­iar to you, that’s because a sequence is basi­cal­ly an IEnumerable<T>!

In the first step of this code I’m build­ing up the fibonac­ci sequence using the Seq.unfold func­tion which giv­en an ini­tial val­ue, gen­er­ates a sequence by con­tin­u­ous­ly apply­ing some com­pu­ta­tion to work out each sub­se­quent ele­ment in the sequence:

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

This sequence, if iter­at­ed through, will con­tain all the num­bers in the fibonac­ci sequence to infin­i­ty, which is why in the next line I’ve spec­i­fied that we should take val­ues from the sequence until the val­ue exceeds 4 mil­lion:

fibonacciSeq
|> Seq.takeWhile (fun n -> n < 4000000)
&#91;/code&#93;

The next two lines then identifies and sums all the even numbers in the sequence:

&#91;code lang="fsharp"&#93;
|> Seq.filter (fun n -> n % 2 = 0) // only interested in even numbers
|> Seq.sum // add them up!