Problem 002

Project Euler

Even Fibonacci numbers

Problem 2

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 this problem, I used the brute force approach by calculating the Fibonacci numbers and testing for even value. Thanks to modern computer, it is really quick but there are better approach.

One thing to notice is the recurring even number on every third Fibonacci numbers. However, how to use this fact to not have to loop until I hit the limit is not clear to me. Secondly, Fibonacci numbers can be estimated from the golden ratio as follow:

F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}

where \varphi = \frac{1+\sqrt{5}}{2} and \psi = \frac{1-\sqrt{5}}{2} .

However, to get the exact value with these facts seem to involve some rounding that may not be quite exact.