How to sum even numbers in a fibonacci list with F#

Question

I'm working through Project Euler to get more practice with F# and I'm getting hung up on the syntax or something with seq. What I'm not understanding is how my first approach is failing:

let generateFibonacci limit =
    let rec genFib a b =
        if a + b < limit then
            seq {
                yield a
                yield! genFib b (a + b)
            }
        else
            []

    genFib 1 2 |> Seq.cache

let getEvenFibsSum =
    generateFibonacci 4_000_000
    |> Seq.filter (fun i -> i % 2 = 0)
    |> Seq.sum

printfn "sum of even fibs: %i" getEvenFibsSum
// result from above is: 1089154
// expected to see: 4613732

I'm recursively iterating, checking the modulo operator for is even, and summing the sequence. In theory this should do the trick just fine. I also printed out the fib sequence as a test and it looked right. However, the sum is obviously way too low. Can someone point out the hole is in what I'm doing? Something is allowing for numbers to be skipped or not reached, but I don't see it yet. Any tips or suggestions appreciated as well.

Answer 1

You're stopping when the sum of a and b exceeds limit, but that's too soon, because you still need to yield a. If you change the test to if a < limit then ..., it works correctly:

let generateFibonacci limit =
    let rec genFib a b =
        if a < limit then
            seq {
                yield a
                yield! genFib b (a + b)
            }
        else
            Seq.empty

    genFib 1 2 |> Seq.cache

let getEvenFibsSum =
    generateFibonacci 4_000_000
    |> Seq.filter (fun i -> i % 2 = 0)
    |> Seq.sum

printfn "sum of even fibs: %i" getEvenFibsSum   // 4613732