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

# First, the recursive definition of the nth fib is O(n), so it won't do.
# I've decided to use Binet's formula, which is an approximation that gives the correct integer.
# The formula is: (Φn - φn)/√ 5, where Φ=(1+√ 5)/2 and φ=(1-√ 5)/2. (Golden Ratio and Inverse)
 
def fibs(n):
    phi = (1 + math.sqrt(5)) / 2
    phi_inverse = (1 - math.sqrt(5)) / 2
    return math.floor( (phi**n - phi_inverse**n) / math.sqrt(5) )
     
if __name__ == '__main__':
    fibslist = []
    for i in range(34): # TODO: Remove this magic number.
        fibslist.append(fibs(i))
    print reduce(lambda x, y: x+y/2, fibslist)
6d13a833d5cc550f7d20357e90db8dbf802ee58b
# 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 math

# First, the recursive definition of the nth fib is O(n), so it won't do.
# I've decided to use Binet's formula, which is an approximation that gives the correct integer.
# The formula is: (Φn - φn)/√ 5, where Φ=(1+√ 5)/2 and φ=(1-√ 5)/2. (Golden Ratio and Inverse)
 
def fibs(n):
    phi = (1 + math.sqrt(5)) / 2
    phi_inverse = (1 - math.sqrt(5)) / 2
    return math.floor( (phi**n - phi_inverse**n) / math.sqrt(5) )
     
if __name__ == '__main__':
    fibslist = []
    for i in range(34): # TODO: Remove this magic number.
        fibslist.append(fibs(i))
    print reduce(lambda x, y: x+y/2, fibslist)