License Public Domain
Lines 88
Keywords
Euler02 (5)
Permissions
Owner: jsimones
Group Owner: SnortSnort
Viewable by Everyone
Editable by All Siafoo Users

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 3 years ago (14 Feb 2013 at 06:22 PM) by msgordon
Holy shit, Jake. You coded the fuck out of this.