🔒 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.

🔐 Key Idea

testing first few iterations for patterns (especially when thousands of iterations are estimated)

🔑 Solution

🧭 Initial idea

$O(n)$ complexity, using recursion.

NOTE: Use loops over recursions for performance.

k = 4000000
sum = 0

def fibo(a, b):
    if a % 2 is 0:
        global sum  # NOTE: Keyword `global` is required to change the global 
                    #       variable in a function in Python.
        sum += a

    if b < k:
        fibo(b, a + b)

fibo(1, 2)

print(str(sum))

4613732

🔁 Loop method (from overview)

$O(n)$ complexity.

a = 1
b = 2
sum = 0

while b < k:
    if b % 2 is 0:
        sum += b
    c = a + b
    a = b
    b = c

print(str(sum))

4613732

🎯 Every third number method (from overview)

$O(n)$ complexity, with 1/3 of the iteration compared to the loop method.

Key idea: testing first few iterations

fibonacci sequence = 1 1 2 3 5 8 13 21 34 55 89 144 ...

sum = 0

a = 1
b = 1
c = a + b

while c < k:
    sum += c  # Third iteration is always even number
    a = b + c
    b = c + a
    c = a + b

print(str(sum))

4613732