Project Euler in F#: Problem 2

Here’s another simple problem, which let me play with another feature of F#:

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.

I’m really liking Visual Studio’s integration with F#. I didn’t know what I’d want to do, but typing ‘Seq.’ gave me a nice list of options; unfold sounded promising, and the type signature made it obvious what I’d need to write.

let ans = Seq.unfold (fun (n,m) -> Some(m,(m, n+m))) (0,1) |> Seq.filter(fun n -> n % 2 = 0) |> Seq.takeWhile((>) 4000000)  |> Seq.sum

An alternate approach is to explicitly generate the sequence.

let rec fib n m = seq{yield m; yield! fib m (n+m)}
let ans = fib 0 1 |> Seq.filter(fun n -> n % 2 = 0) |> Seq.takeWhile((>) 4000000)  |> Seq.sum

Unlike problem 1, there are no performance surprises here: both of these solutions have the same performance, as does using Seq.initInfinite. Of course, the performance could be improved by getting rid of the mod operation and only generating the even numbers (which is easy to do, since every third item in the sequence is even).

Advertisements
Project Euler in F#: Problem 2

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s