3
\$\begingroup\$

Project Euler Problem 2 asks for the sum of all even Fibonacci numbers below 4 million.

My first attempt at this problem using functional programming with F#. I would've liked to use some kind of take-while function to keep generating Fibonacci numbers until they fulfilled certain conditions, but alas I could not find such a thing in F#.

open System

let rec fib n = match n with
                | 0 | 1 | 2 -> n
                | _ -> fib (n - 1) + fib (n - 2)

let rec nOfFibTermsUpUntil x y = if fib (y + 1) < x then nOfFibTermsUpUntil x (y + 1) else y

[for n in 0..nOfFibTermsUpUntil 4000000 0 -> fib n]
|> List.filter (fun x -> x % 2 = 0)
|> List.sum
|> printf "The sum of Fibonacci terms up until 4,000,000 is: %d"
Console.ReadKey () |> ignore
\$\endgroup\$
5
\$\begingroup\$

I discovered an (arguably) better way of doing this in F# using Seq.unfold and tuples. I'll post the solution below.

open System

(1,1) |> Seq.unfold (fun (a, b) -> Some(a + b, (b, a + b)))
|> Seq.takeWhile (fun x -> x <= 4000000)
|> Seq.sumBy (fun x -> if x % 2 = 0 then x else 0)
|> printf "The sum of Fibonacci terms up until 4,000,000 is: %d"
Console.ReadKey () |> ignore
\$\endgroup\$
  • 1
    \$\begingroup\$ Technically, you're supposed to takeWhile x < 4000000 (not x <= 4000000) — not that it matters, since 4000000 is not a Fibonacci number. \$\endgroup\$ – 200_success Nov 2 '14 at 8:00
  • \$\begingroup\$ Yeah, I think using seq instead of list is the right way here: you can't have a potentially infinite list, but you can do that with seq. \$\endgroup\$ – svick Nov 4 '14 at 22:35
1
\$\begingroup\$

Your base case of fib(2) = 2 is incorrect. No variant of the Fibonacci Sequence starts with 0, 1, 2,…. You just happen to get the same answer because the problem only cares about the even-valued terms.

To take the terms under 4 million, use Seq.takeWhile.

\$\endgroup\$
  • \$\begingroup\$ You're right, removing that base case will still yield the correct answer and a valid Fibonacci sequence. \$\endgroup\$ – Overly Excessive Nov 2 '14 at 7:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.