Problem 2

Problem: Find the sum of all the even numbers in the Fibonacci sequence whose values do not exceed 4 million.

Q: What is the minimum section of the sequence that we need to keep in memory at any one time?
A: 3 elements – current element and previous two elements (which are used to calculate the current element).

Q: What is the starting point?
A: 1, 1, 2 (the first three elements).

Q: What is the rule to update the elements?
A: Remove element 0, push elements 1 and 2 back one space, recalculate the new element 2 as the sum of elements 0 and 1.

Solution:

max_number = 4000000
fib_sequence = [1, 1, 2]
total = 0

while fib_sequence[2] <= max_number:
  if fib_sequence[2] % 2 == 0:
      total += fib_sequence[2]

  # Move all elements back one place and recalculate the 3rd
  fib_sequence[0] = fib_sequence[1]
  fib_sequence[1] = fib_sequence[2]
  fib_sequence[2] = fib_sequence[0] + fib_sequence[1]

print("Total of all even Fibonnaci numbers up to " + str(max_number) + " is: " + str(total))