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.
The 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).
Project Euler 2 SolutionRuns < 0.001 seconds in Python 2.7.
Use this link to get the Project Euler 2 Solution Python 2.7 source.
AnswerSlowly 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.
- Good explaination on Fibonacci multiples: Fibonacci mod k, by Robert McCann, Univ. of Toronto Bahen Centre
- Reference: The On-Line Encyclopedia of Integer Sequences (OEIS) A000045: Fibonacci numbers: F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1.
- For a limit of 4,000,000 the loop iterates 11 times.
- The approximate ratio between two consecutive terms in the Fibonacci sequence is the golden ratio (phi, or φ ≈ 1.618034).
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:
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)