Euler2.py

""" Even Fibonacci numbers
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.
Ricky Kwok rickyk9487@gmail.com

Mathematical solution:
1. Every third Fibonacci number (with fib(1) = fib(2) = 1) is even.
2. Using the definition of the Fibonacci numbers, the sum of all evens up to N 
   is equal to one-half times the sum of all Fibonacci numbers up to N.
3. With z = math.sqrt(5), xplus = (1+z)/2.0, xminus = (1-z)/2.0, an explicit 
   formula is
y =(1/2.0)*(1/z)*((1-xplus ** 4000000)/(1-xplus) - (1-xminus ** 4000000)/(1-xminus))
which can be computed in time O(1). The solution below is O(n)
"""
# 4613732
f1, f2, sum = 0, 1, 0
while f1 < 4000000:
    f1, f2, sum = f2, f1 + f2, sum + f1
print sum/2