h4ck3r.net

Euler Problem 2

10 May 2008

(only 191 problems to go, currently)

Problem #2 was stated as:

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.

Pretty straightforward I guess.

let rec fib n = if n else fib(n-1) + fib(n-2)

[1..40]
|> Seq.map(fib)
|> Seq.filter(fun x -> x < 4000000 && x % 2 = 0)
|> Seq.sumByInt(fun x -> x)

I was wondering if the 4,000,000 was supposed to try to make me do something “smart” because it was intended to take a long time. But, I didn’t and it took about a second on my computer, even with the very dumb fib.

The weakest part is the “40”, but I feel like F# earned me that because after I typed in the definition of fib, I used the awesome FSI (interactive F# window in Visual Studio) to quickly test what numbers would make sure I got up to at least 4M (it was 33, but 40 seemed less sneaky).

There’s probably a better way to do the last line too, I guess fold over + would work. I was sort of hoping for a default Seq.sum without arguments, but I guess not. Maybe there’s a shorthand way of writing the identity function?