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

"""
OBSERVATION: every 3rd Fibonacci term is even, and follows a pattern such that:
Assume FE[] is an array of Even valued Fibonacci numbers.
Let n = 1 and let FE[0] = 0
Then by induction, FE[n+1] = (FE[n] * 4) + FE[n-1] as FE[n]
"""


def getSumOfEvenFibonacciValuesToLimit(limit): 
    total = 0
    prev = 0 
    current = 2 #we know the first even value Fibonacci term is 2, so we start there to begin the cycle

    while (current <= limit):
        total += current  #Since the current value is still under the limit, we are safe to add it to the total

        temp = current * 4 + prev #Find the next term (See OBSERVATION)
        prev = current 
        current = temp
        
    return total
    
print(getSumOfEvenFibonacciValuesToLimit(4000000))

#Python Lesson:  A comment block is made by wrapping the text in """ """ 

