## Second Problem: Even Fibonacci numbers

The second problem in the Euler project is a bit more challenging:

Even Fibonacci Numbers
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.

For a fast solution, I will use the following closed forms for Fibonacci numbers $F_n:$ If $\varphi = \frac{1+\sqrt{5}}{2},$ and $\psi = \frac{1-\sqrt{5}}{2},$ then $F_n = \frac{\varphi^n-\psi^n}{\sqrt{5}}=\big[ \frac{\varphi^n}{\sqrt{5}} \big].$ With these formulas, it is assumed that $F_0=0, F_1=1, F_2=1$ and $F_3=2.$

We may find with the second form above, the index $M$ of the Fibonacci number right before four million:

$\frac{\varphi^M}{\sqrt{5}} \leq 4\cdot 10^{6} \le \frac{\varphi^{M+1}}{\sqrt{5}}.$

Or similarly,

$M \leq \frac{6+\log_{10} 4\sqrt{5}}{\log_{10} \varphi} \le M+1.$

We may then choose $M = \lfloor \frac{6+\log_{10} 4\sqrt{5}}{\log_{10} \varphi} \rfloor = 33.$ This is, of course, accurate:

$F_{33}=3\,524\,578, F_{34}=5\,702\,887.$

We are ready to compute the sum of the even-valued Fibonacci numbers that do not exceed four million, which are those with indices $3+3n$ for any $0 \leq n \leq 10:$

$\displaystyle{\sum_{n=0}^{10} F_{3+3n} = \frac{1}{\sqrt{5}} \sum_{n=0}^{10} \big( \varphi^{3+3n} - \psi^{3+3n} \big) = \frac{\varphi^3}{\sqrt{5}} \frac{1-\varphi^{33}}{1-\varphi^3} - \frac{\psi^3}{\sqrt{5}} \frac{1-\psi^{33}}{1-\psi^3}}$

Piece of cake for julia:

julia> phi=0.5*(1+sqrt(5))
1.618033988749895

julia> psi=0.5*(1-sqrt(5))
-0.6180339887498949

julia> phi^3/sqrt(5)*(1-phi^33)/(1-phi^3)-psi^3/sqrt(5)*(1-psi^33)/(1-psi^3)
4.613732000000005e6


The answer is the number 4 613 732.

1. No comments yet.
1. January 9, 2013 at 10:16 am