Project Euler #2 in F#

Question

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

Overly Excessive · Accepted Answer · 2014-11-02 07:27:14Z

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

Technically, you're supposed to takeWhile x < 4000000 (not x <= 4000000) — not that it matters, since 4000000 is not a Fibonacci number. — 200_success
– 200_success, Commented Nov 2, 2014 at 8:00
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. — svick
– svick, Commented Nov 4, 2014 at 22:35

200_success · Accepted Answer · 2014-11-02 00:53:09Z

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.

You're right, removing that base case will still yield the correct answer and a valid Fibonacci sequence. — Overly Excessive
– Overly Excessive, Commented Nov 2, 2014 at 7:19

daveyost · Accepted Answer · 2023-02-19 20:46:53Z

The explicit names for things here hopefully show more clearly how unbind works.

let fibonacciSeq = let generator state = let (cur, prev) = state let next = cur + prev let state' = (next, cur) Some (cur, state') let more = (1, 0) |> Seq.unfold generator seq { 0 yield! more }

Stack Exchange Network

Project Euler #2 in F#

3 Answers 3

You must log in to answer this question.

Hot Network Questions

Project Euler #2 in F#

3 Answers 3

You must log in to answer this question.

Related

Hot Network Questions