Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

python
project euler
community creator

Project Euler 002

Armaan Nougai

Problem statement

Each new term in the Fibonacci sequence is generated by adding the previous two terms. If you start 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.

Overview

So, basically, the problem says that we have to compute a special sequence (i.e., the Fibonacci sequence) until its last term exceeds 4 million, and then calculate the sum of even numbers of that sequence.

A Fibonacci Sequence is a series of numbers in which each Fibonacci number is the sum of the two preceding numbers. The simplest sequence is the series 1, 1, 2, 3, 5, 8, etc.

1 of 5

Approach 1

We will first apply the brute force approach, i.e., we will keep track of the sum of even valued terms while calculating the required series.

limit = 4000000
sum = 0
a = 1
b = 1
while b < limit:
  
  if b % 2 == 0 : sum += b
  h = a + b
  a, b = b, h
  
print(sum)

Approach 2

Now, let’s try to get rid of the testing for even values. Here is the beginning of the Fibonacci sequence, even numbers are in bold:

1 1 2 3 5 8 13 21 34

It is easy to prove that every third Fibonacci number is even. Now, let us improve our program from checking if its even or not to just adding every third number.

limit = 4000000
sum = 0
a = 1
b = 1
c = a+b
while c < limit:
  
  sum += c
  a = b + c
  b = c + a
  c = a + b
print(sum)

Approach 3

There is another beautiful structure hidden beneath this problem:

If we only write the even numbers of the Fibonacci series:

2 8 34 144…

Here, 34 = 48 + 2 144 = 434 + 8

It seems that they obey the following recursive relation:

E(n) = 4*E(n-1) + E(n-2)

This makes the problem a lot clearer, and now we don’t even have to calculate the whole Fibonacci series. We’ll just create a series with the above equation.

limit = 4000000
a = 2
b = 8
c = 34
sum = 10
while c < limit:
  sum += c
  a = b
  b = c
  c = 4 * b + a
  print(a,b,c)

print(sum)

RELATED TAGS

python
project euler
community creator
RELATED COURSES

View all Courses

Keep Exploring