Felix Ayoola
By Felix Ayoola

Solving Project Euler's Problem 2 with Python

Solving Project Euler's Problem 2 with Python

Project Euler

let us first learn what the Project Euler is:

Project Euler is a website dedicated to a series of computational problems intended to be solved with computer programs. The project attracts adults and students interested in mathematics and computer programming. Since its creation in 2001 by Colin Hughes, Project Euler has gained notability and popularity worldwide.

why Python?

I find Python to be very simple and its syntax is very close to english.

What is the problem?

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

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

How do we approach this problem?

  1. The first step in solving any problem, is to understand the problem first, make sure you can communicate the problem to someone else in your own way without losing the focus.

  2. Write down the problem in pseudocode, this is more like english, so for example you might start this problem’s pseudocode like this

    1. Create the fibonnaci sequence with terms up to but not including four million,

    2. Check if each term is a even number,

    3. Add all the numbers that fulfils (2) and print the sum

Create an algorithm to implement in your code

This would be a step by step process on how you intend to write the code that solves the problem.

Let us write and algorithm for our problem:

  1. Create the function for the fibonnaci series,

this function returns:

1
2
3
4
5
    return 1 for the first term

    return 1 for the second term

    for terms after the second return their value as the sum of the two values before them
  1. Initiate the a variable ‘sum’ to hold the summation of the even fibonnaci numbers

  2. Initiate a varible ‘n’ to indicate the number of a corresponding term in the fibonnaci series

  3. Check if the value of the term is less than 4000000, if true,

  4. Check if the fibonacci term is even, if true

  5. Add the value to the variable ‘sum’

  6. If the number is less than four million, Increament ‘n’ and repeat steps 1 through 6 untill a term that is equal or greater than four million is reached.

Note

I don’t always go through this process religiously, so don’t worry yourself, look at the problem and do whatever works for you. Just make sure you solve the problem.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#Create the function for the fibonnaci series

#Name the function

def fibonacci(n):

    #the first term of the fibonnaci series is 1

    if n == 1:

        return 1

    #the second term of the fibonnaci series is 1

    elif n == 2:

        return 1

    #for terms after the second their value is the sum of the two values before them

    elif n > 2:

        return fibonacci(n-1)+ fibonacci(n-2)



#initiate the sum variable

sum = 0

#initiate the position variable of terms

n = 1

#Check if the value of the term is less than 4000000

while fibonacci(n) <= 4000000:

    #Check if the fibonacci term is even

    if fibonacci(n)%2==0:

        #if that is true add it to the sum

        sum = sum + fibonacci(n)

    #increament the position varible to move to the next term

    n += 1

#print the sum variale which by now contains the sum of all even fibonacci terms below 4000000

print(sum)

Optimization using Cache

While the code above will solve the problem, you’ll notice that your system will slow down and it might take a while before you get the solution. This is due to the fact that the fibonnaci series is a recursion problem…like a Russian doll, in which one doll (fibonnaci term) is dependent on the another term.

Example:

fibonnnaci(5) = fibonacci(4) + (fibonnaci 3)

fibonnacci(4) = fibonnacci(3) + fibonnaci(2)

fibonnaci(3) = fibonnaci(2) + fibonnaci(1)

Hence; fibonnaci(5) = fibonnaci(2) + fibonnaci (2) + fibbonaci(1) + fibonnaci(2) + fibonnaci(1)

You’ll notice that no matter how big the term is, you have to break it down to fibonnaci(2) and fibonnaci(1) this is recursion and this process is slow.

Luckily, Pythonb has a solution that can help, which is by using memoization, so if you asked fibonnaci(5), python won’t recalculate fibonnaci(4) since it knows the value from previous calcualtions in the series. The module for this is the lru_cache. This will make the program run faster.

let’s implement this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#import lru_cache to prevent your system from slowing down due to recurssion of the fibonnaci series

from functools import lru_cache



#specify the maxsize of the cache

@lru_cache(maxsize=1000)



#Create the function for the fibonnaci series

#Name the function

def fibonacci(n):

    #the first term of the fibonnaci series is 1

    if n == 1:

        return 1

    #the second term of the fibonnaci series is 1

    elif n == 2:

        return 1

    #for terms after the second their value is the sum of the two values before them

    elif n > 2:

        return fibonacci(n-1)+ fibonacci(n-2)



#initiate the sum variable

sum = 0

#initiate the position variable of terms

n = 1

#Check if the value of the term is less than 4000000

while fibonacci(n) <= 4000000:

    #Check if the fibonacci term is even

    if fibonacci(n)%2==0:

        #if that is true add it to the sum

        sum = sum + fibonacci(n)

    #increament the position varible to move to the next term

    n += 1

#print the sum variale which by now contains the sum of all even fibonacci terms below 4000000

print(sum)

Conclusion:

So this was a 1-minute (maybe more) read article on using Python to solve Project Euler’s Problem 2 and I also try to show the need for optimisation by using cache. There is no one way to solve this problem, you can choose to use a diffrent approach, it depends on you. I hope this article helps you to get started with using python to solve problems, you can try the more difficult ones, I should be adding another article on another problem soon.

Thank you!!