Project Euler Q2 - Sum of even Fibonacci numbers

Question

I'm very new at F#, and am using Project Euler to help me learn. Question #2 kept me going for a while, as my initial attempt at an answer was very slow and inelegant. Then I learnt about Seq.unfold, and a whole new vista unfolded in front of me!

The problem statement is as follows (source):

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.

Please can you comment on this code. Bear in mind I'm very new at this, so I may be doing it completely wrong!

let fibEvenSum max =
 let rec fibEven n =
 match n with
 | 0 -> 0
 | 1 -> 2
 | n -> 4 * (fibEven (n - 1)) + (fibEven (n - 2))
 1 |> Seq.unfold (fun n -> Some(fibEven n, n+1))
 |> Seq.takeWhile (fun n -> n < max)
 |> Seq.sum

If I run it like this, I get the right answer:

sumOfEvenFibs 4000000I

Is there a better way to do it?

• Sumurai8: I have suggested a change to your question that changed a couple of things. Your title did not tell us what your code was supposed to do. We all ask questions here expecting comments or useful insight on our code. Adding "comments please" to the title is therefore not very useful. Similarly, your question did not contain the problem definition of the problem you tried to solve. If we do not know what the code should solve, it is harder to comment on it telling you what you could possibly improve.
• Avrohom Yisroel: @Sumurai8 No problem, I'm new to this site, so all suggestions welcome! Why did you remove the project-euler tag though? That seemed pretty relevant to me.
• wentimo: I would suggest using this equation to solve it instead of iterating over the entire fibonacci sequence : Fib(x + 6) = 4*Fib(x+3) + Fib(x) - This allows you to skip over calcluating the odd number fibonacci.
• Avrohom Yisroel: @wentimo Wow, I didn't know about that formula! That makes the problem more interesting, and should make the calculation faster. I'll have a play and maybe update my code. Thanks for that.
• Avrohom Yisroel: @Jamal Why did you remove my first solution? I'm still interested in hearing comments on it, especially as it was shorter than the second one, and no slower.

Answer 1

Daniel's solution to another question applies here equally.

On another question, I showed that the sum is equal to

$$ \frac{F_{3n+2} - 1}{2} $$

where \3ドルn\$ is the largest multiple of \3ドル\$ not to exceed the maximum.

If you wish to use this for asymptotic improvements, note that since the Fibonacci sequence has a closed-form solution, you can use it to find an approximate bound for \3ドルn\,ドル and then use fast exact mechanisms to find the exact value of \$F_{3n+2}\$.

$$ F_{3n} \approx \phi^{3n}/\sqrt 5 \\ 3n \approx \log_\phi \left(F_{3n} \sqrt 5 \right) $$

Finding a lower bound for \$n\$ thus takes very little time.

Personally I'd stick with the simple, slower solution, but it's interesting to note how far you can get with a bit of mathematical analysis.