// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (16 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 problem is asking to consider all Fibonacci numbers less than or equal to 4 million and sum the even numbered ones.

The sequence is formally defined by the recurrence relation:

F_1=1, F_2=1, F_n=F_{n-1}+F_{n-2}

The Fibonacci sequence enumerated 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.

This is because adding two odd numbers (1+1) sum to an even number, followed by adding 2 sets of even and odd numbers (1+2 and 2+3) which sum to an odd number. This principle propagates through the series ad infinitum. A good explaination on Fibonacci multiples, such as the even ones, is provided in the paper: Fibonacci mod k, by Robert McCann, Univ. of Toronto Bahen Centre.

To solve, we will need a program for this limit of 4×106 and the hackerRank Project Euler 2 version which requires us to test 100,000 problems at once with a more ambitious limit of 4×1016 in less than a second. We can bypass iterating the full sequence and just focus on every third term.

This can be easily achieved by defining a new generalized Fibonacci sequence of even Fibonacci numbers starting from zero as: {0, 2, 8, 34, 144, 610, … }.

G_0=0, G_1=2, G_n = 4G_{n-1} + G_{n-2}

This works very well, requiring only 11 iterations for a limit of 4×106 and 27 iterations for 4×1016.

Project Euler 2
This program and method
solves all test cases for
Project Euler 2 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

Project Euler 2 Solution last updated

Discussion

No comments yet.

Post a comment