Project Euler Q2 - Sum of even Fibonacci numbers 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 -&gt; 0
    | 1 -&gt; 2
    | n -&gt; 4 * (fibEven (n - 1)) + (fibEven (n - 2))
  1 |&gt; Seq.unfold (fun n -&gt; Some(fibEven n, n+1))
    |&gt; Seq.takeWhile (fun n -&gt; n &lt; max)
    |&gt; Seq.sum


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

sumOfEvenFibs 4000000I


Is there a better way to do it?
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 \$3n\$ 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 \$3n\$, 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.