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))

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

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

The answer is the number 4 613 732.

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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: