// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (14 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 2 Solution

Project Euler 2 Solution

Project Euler 2: Find the sum of the even-valued terms in the Fibonacci sequence


Project Euler 2 Problem Description

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

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

Analysis

foxtrot20051011The Fibonacci sequence is: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610 and every third number is even. All the rest are odd. Read the document in the afterthoughts section below for a good explanation of why this is.

To solve, sum every third number of the sequence that’s less than 4 million.

Example for L<400: The first even Fibonacci number to exceed 400 is 610. That terminates the loop and we are left with x=144 and y=610. 610+144 = 754, 754-2 = 752, and finally 752/4 = 188; the sum of all even Fibonacci numbers less than 400 (2+8+34+144 = 188).

h_mark_sm-05bceb881aa02b72d688d21db01df5d8
This program and method
solves all test cases
on HackerRank

Project Euler 2 Solution

Runs < 0.001 seconds in Python 2.7.
download arrowUse this link to get the Project Euler 2 Solution Python 2.7 source.

Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
|4613732|

Afterthoughts

Phi is calculated as
\frac{1+\sqrt5}{2}

The Fibonacci Series and the Golden Spiral

A Golden spiral is very similar to the Fibonacci spiral but is based on a series of identically proportioned golden rectangles, each having a golden ratio of 1.618 of the length of the long side to that of the short side of the rectangle:

Project Euler 2: Golden Spiral

The Fibonacci spiral gets closer and closer to a Golden Spiral as it increases in size because of the ratio of each number in the Fibonacci series to the one before it converges on Phi, 1.618, as the series progresses (e.g., 1, 1, 2, 3, 5, 8 and 13 produce ratios of 1, 2, 1.5, 1.67, 1.6 and 1.625, respectively)

Project Euler 2 Solution last updated

Discussion

No comments yet.

Post a comment