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.

### Like this:

Like Loading...

*Related*

## Leave a Reply