Lines 88
Euler02 (5)
##### Permissions
Owner: jsimones
Group Owner: SnortSnort
Viewable by Everyone
Editable by All Siafoo Users

# Project Euler 2 0

 Language Python
# 's
`  1"""  2Even Fibonacci numbers  3Problem 2  4Each new term in the Fibonacci sequence is generated by adding the previous two  5terms. By starting with 1 and 2, the first 10 terms will be:  6  71, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...  8  9By considering the terms in the Fibonacci sequence whose values do not exceed 10four million, find the sum of the even-valued terms. 11 12""" 13import numpy as np 14 15def Fibonacci_1(nterms): 16    """ 17    Literal implementation using a for loop and the __builtin__.sum function. 18 19    """ 20    x = [1, 2] 21    for i in range(nterms - 2): 22        x.append(sum(x[-2:])) 23    return x 24 25def Fibonacci_2(nterms): 26    """ 27    Using Binet's formula (http://en.wikipedia.org/wiki/Fibonacci_number) 28    instead of recurrence relation. Much faster than Fibonacci_1. 29 30    Could have used an explicit for loop block instead of list comprehension; 31    time difference is trivial. 32 33    """ 34    a, b = (1 + 5**0.5) / 2, (1 - 5**0.5) / 2 35    return [int((a**(i+2) - b**(i+2)) / 5**0.5) for i in range(nterms)] 36 37def Fibonacci_3(nterms): 38    """ 39    numpy version of Fibonacci_2. Note that the ruturned type is a float array. 40    Faster than Fibonacci_2 when nterms is large. 41 42    """ 43    a, b = (1 + np.sqrt(5)) / 2, (1 - np.sqrt(5)) / 2 44    x = np.arange(nterms) + 2 45    return (a**x - b**x) / np.sqrt(5) 46 47def nterms_finder(func, thresh, nterms=10, step=10): 48    """ 49    Return the largest number of terms for which all terms in the monotonic 50    sequence returned by func are less then thresh. 51 52    """ 53    while 1: 54        x = int(func(nterms)[-1]) 55        if step == 1 or x == thresh: 56            return nterms 57        elif x < thresh: 58            nterms += step 59        elif x > thresh: 60            step /= 2 61            nterms -= step 62 63def even_sum_1(x): 64    """ 65    Incremental approach with for loop. 66 67    """ 68    s = 0 69    for i in x: 70        if i % 2 == 0: 71            s += i 72    return s 73 74def even_sum_2(x): 75    """ 76    Generator expression to "filter" even values of x, then sum. Slightly slower 77    than even_sum1. 78 79    """ 80    return sum(i for i in x if i % 2 == 0) 81 82def even_sum_3(x): 83    """ 84    Generator expression to set odd values of x to 0, then sum. Slightly slower 85    than even_sum2. 86 87    """ 88    return sum(i * (1 - i % 2) for i in x) 89 90def even_sum_4(x): 91    """ 92    numpy version of even_sum_3. Faster than even_sum_1 when x.size is large. 93 94    """ 95    return np.sum(x * (1 - np.mod(x, 2))) 96 97def even_sum_5(x): 98    """ 99    Fancy indexing to pick out even values. A little faster than even_sum_4.100101    """102    return np.sum(x[np.mod(x, 2) == 0])103104def main():105    thresh = 4e6106    nterms = nterms_finder(Fibonacci_3, thresh)107    x = Fibonacci_3(nterms).astype('int')108    s = even_sum_5(x)109    print s110111if __name__ == '__main__':112    main()`