Project Euler problem 2

Source code available on GitHub.

The second problem is not much harder:

  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:  \begin{center} 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... \end{center}  By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

We basically want to run through the Fibonacci sequence until we hit 4 million, all the while adding every even-valued term to a running sum.

So, we start by defining the first two terms of the sequence as 1 and 2 and then making a rule to generate the rest. Making an empty list fibonacci = [0,0], we set fibonacci[0] = 1 and fibonacci[1] = 2. Now, we want to implement a loop that will keep going until we tell it to stop. For this we can use while True:, as since True is always true, the loop will always keep running.

That means we’ll have to do our incrementing manually, unlike a for loop. Setting our index as i = 2 (the third term in the sequence, as we’ve defined the first two), we’ll do stuff in the loop and then increment it by one using i += 1 at the end:

fibonacci = [0,0]
fibonacci[0] = 1
fibonacci[1] = 2

i = 2
while True:
    stuff
    i += 1

Next, we want to define the rule to keep the sequence going. Since each term is the sum of the previous two, we know that fibonacci[i] == fibonacci[i-1] + fibonacci[i-2] for every i. The catch is, the list fibonacci doesn’t actually have an index i yet, so we need to append this value to the end of the list instead:

fibonacci = [0,0]
fibonacci[0] = 1
fibonacci[1] = 2

i = 2
while True:
    fibonacci.append(fibonacci[i-1] + fibonacci[i-2])
    i += 1

Nice. We know we only want to go up to 4 million, so if we reach or exceed that number we use break to terminate the while loop:

if fibonacci[i] >= 4000000:
        break

All that’s left is our actual task: sum all the even terms. Taking a similar approach to problem 1, we initialise a variable called summation and every loop, if the current term is even, we add it in.

Add print(summation) at the end and we’re done!

fibonacci = [0,0]
fibonacci[0] = 1
fibonacci[1] = 2
summation = 0
i = 2
while True:
    fibonacci.append(fibonacci[i-1] + fibonacci[i-2])
    if fibonacci[i] >= 4000000:
        break
    if fibonacci[i] % 2 == 0:
        summation += fibonacci[i]
    i += 1
print(summation)

Leave a Reply

Your email address will not be published. Required fields are marked *