(3 votes, average: 5.00 out of 5)

## Project Euler Problem 2 Solution

#### Problem Description

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, …

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

#### Analysis

Fibonacci sequence is: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 and every third number is even. All the rest are odd. To solve, just iterate the sequence and add every third number.

#### Solution

Runs < 1 second in Python.

```limit = 4000000 x, y, sum = 1, 1, 0   while (sum < limit): sum += (x + y) x, y = x + 2*y, 2*x + 3*y   print "Answer to PE2 = ", sum```

Older deprecated code below. Included here as a reference.
Runs < 1 second in Python.

```limit = 4000000 phi_cubed = ((1+5**.5)/2)**3 #golden ratio cubed   f = 2 sum = 0 while f < limit: sum += f f = round(f * phi_cubed) print "Answer to PE2 = ", int(sum)```

The approximate ratio between two consecutive terms in the Fibonacci sequence is the golden ratio (phi, or φ ≈ 1.618034). It can also be demonstrated that every third term of the sequence are the only even numbers. By combining this knowledge we can calculate the series of even Fibonacci numbers by multiplying the previous even term in the series by the cube of the golden ratio.

EDIT: Although the above is a novel solution, it was proven that just adding every third term of the sequence was more efficient (Thanks, Robert.)

For a limit of 4,000,000 the loop iterates 11 times.

## Discussion

### 3 Responses to “Project Euler Problem 2 Solution”

1. Your method is neat, but it’s not particularly efficient; your use of floating points and rounding operations results in your code taking TWICE as long as a more primitive algorithm involving going through each Fibonacci number and merely adding up the even ones.

Posted by Robert Darkins | August 14, 2009, 8:20 AM
• Thanks for the comment Robert. I never thought of that! I will post some timings for this limit and larger ones to see if this technique is worth it.

Posted by Mike | August 15, 2009, 11:43 PM
• Well, after testing Robert’s claim, I have to agree.

Posted by Mike | December 15, 2010, 1:29 PM