F# Project Euler Problem 2

Solving second problem for Project Euler Problem 2 is an interesting one.

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, …
By considering the terms in the Fibonacci sequence whose
values do not exceed four million, find the sum of the even
valued terms.

Challenge here is to generate a fibonacci sequence, which is the fib(n-1) + fib(n-2) formula. This generates a evaluation tree during recursion and becomes quite large when generating a large N fibonacci value, and stackoverflow happens. To tackle this problem in a more efficient way, we shouldn’t generate the number for N re-cursing backwards, but generate the number from summation forwards.

Here’s my first F# solution I came up with.

let initiniteFib =
    let rec fib1 n1 n2 =
        seq {
            yield n1
            yield! fib1 n2 (n1+n2)
    fib1 0I 1I

let answer = initiniteFib 
                |> Seq.takeWhile (fun x -> x < 4000000I)
                |> Seq.filter (fun x -> x % 2I = 0I)
                |> Seq.sum

Another way to solve the same problem, is using Seq.unfold.

let answer = Seq.unfold (fun (first, second) -> Some(second, (second, first+second))) (0I, 1I)
                |> Seq.takeWhile (fun x-> x < 4000000I)
                |> Seq.filter (fun x -> x % 2I = 0I)
                |> Seq.sum

If you have more interesting ways to solve this, please share.


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

%d bloggers like this: