License Public Domain
Lines 88
Keywords
Euler02 (5)
Permissions
Owner: jsimones
Group Owner: SnortSnort
Viewable by Everyone
Editable by All Siafoo Users
Hide
Siafoo is here to make coding less frustrating and to save you time. Join Siafoo Now or Learn More

Project Euler 2 Atom Feed 0

# '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.
100
101 """
102 return np.sum(x[np.mod(x, 2) == 0])
103
104def main():
105 thresh = 4e6
106 nterms = nterms_finder(Fibonacci_3, thresh)
107 x = Fibonacci_3(nterms).astype('int')
108 s = even_sum_5(x)
109 print s
110
111if __name__ == '__main__':
112 main()

Comments

over 5 years ago (14 Feb 2013 at 06:22 PM) by msgordon
Holy shit, Jake. You coded the fuck out of this.