#################################################################################################################################################
#
#                Project Euler problem 2
#
#   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.
#
#
#
#################################################################################################################################################
import time
# ITERATIVE Solution, better runtime.  Complexity for iterative solution is O(n), whereas recursive would be O(2**n)
# just to generate Fibonacci numbers.
iterativeStart = time.time()
def iterativeFibonacci():

    fib1 = 1
    fib2 = 2
    nextFib = 0
    sumOfEvens = 2

    while nextFib < 4000000:
        nextFib = fib1 + fib2
        if nextFib % 2 == 0:
            sumOfEvens += nextFib
        fib1 = fib2
        fib2 = nextFib

    return sumOfEvens


if __name__ == "__main__":
    print("iterative answer is {}, run time is {} seconds".format(iterativeFibonacci(), time.time() - iterativeStart))
