Yesterday’s post was just an easy warm-up. We’re just getting started!

Problem 2

Sum all even numbers in the Fibonacci sequence (1, 1, 2, 3, 5, 8, 13…) below 4 million.

C# Solution

The C# solution to this is fairly straightforward.

var elem1 = 1;
var elem2 = 1;
var sum = 0;
while (elem2 < 4000000)
{
	var newElem = elem1 + elem2;
	if (newElem%2 == 0) sum += newElem;
	elem1 = elem2;
	elem2 = newElem;
}
Console.WriteLine(sum);

F# Solution

This F# uses a sequence generator to create an infinite sequence of Fibonacci numbers and uses the pipe operator to apply the different constraints of the problem:

• Numbers below 4,000,000
• Only even numbers

Incidentally, I’m using an “old school” trick here to determine if the number is even. If you do a bitwise and operation on a number with 1, the result is 0 if the number is even and the result is 1 if it’s odd. The optimizing compiler probably already does this when you write i % 2 = 0 but old habits die hard.

let fibSeq =
    let rec fibSeq n1 n2 = 
        seq { let n0 = n1 + n2 
              yield n0
              yield! fibSeq n0 n1 }
    seq { yield 1 ; yield 1 ; yield! (fibSeq 1 1) }

let isEven i = i &&& 1 = 0

fibSeq
|> Seq.filter (fun x -> x < 4000000)
|> Seq.filter isEven
|> Seq.sum

But there’s a bug here. Can you spot it?

The first call to Seq.filter is wrong. This tells F# to go through every item in the sequence and apply the filter function. Since our sequence is infinite, we’ll eventually get an arithmetic overflow.

Since we know that the sequence is in numeric order, we can use Seq.takeWhile instead of Seq.filter for the first constraint.

fibSeq
|> Seq.takeWhile (fun x -> x < 4000000)
|> Seq.filter isEven
|> Seq.sum