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

# My original brute-force approach
f0 = 0
f1 = 1
f2 = f0 + f1
sum = 0

while f2 < 4000000:
    f0 = f1
    f1 = f2
    f2 = f0 + f1

    if f2 % 2 is 0:
        sum += f2

print sum  # 4613732

# A more efficient approach recognizes that every third number in the sequence (starting from 2) is even
# and that each of these values (i'll call as En) is equal to four times the value of the previous even number (En-1)
# plus the even number immediately preceding En-1: i.e. En = 4 * En-1 + En-2.
# e.g. at the top this file the value 34 can be calculated as 4 * (8) + (2).
# This approach only requires a handful of calculations in comparison to the original brute-force

e0 = 0
e1 = 2
sum = 0

while e1 < 4000000:
    sum += e1
    nextFib = 4 * e1 + e0
    e0 = e1
    e1 = nextFib

print sum  # 4613732

# Alternate means of doing the above using an array which has the added benefit of storing all the even numbers
# of the fibonacci series under 4000000
even_fibs = [0, 2]  # initialize array with first two even numbers of the fib series
tail = len(even_fibs) - 1
sum = 0

while even_fibs[tail] < 4000000:
    sum += even_fibs[tail]
    even_fibs.append(4 * even_fibs[tail] + even_fibs[tail - 1])
    tail += 1

print sum  # 4613732
