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

CONTRIBUTOR

Armaan Nougai
RELATED COURSES

View all Courses

Keep Exploring

Learn in-demand tech skills in half the time 