• API
• FAQ
• Tools
• Archive
SHARE
TWEET # rowland.py a guest Nov 14th, 2010 64 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #!/usr/bin/env python2.6
2. """
3. rowland.py
4. See http://programmingpraxis.com/2010/11/12/rowlands-prime-generating-function/
5.
6. We make heavy use of memoization in order to trade space for time whenever we
7. define a recursive function or a function that is used by another.
8.
9. GRE, 11/14/10
10. """
11.
12. import time
13. import functools
14.
15. def gcd(a, b):
16.    while b:
17.        a, b = b, a % b
18.    return a
19.
20. def memoize(func):
21.     func.memo = {}
22.     def memoizer(arg):
23.         try:
24. # Try using the memo dict, or else update it
25.             return func.memo[arg]
26.         except KeyError:
27.             func.memo[arg] = result = func(arg)
28.             return result
29.     return functools.update_wrapper(memoizer, func)
30.
31. @memoize
32. def a106108(n):
33.     if n == 1:
34.         return 7
35.     else:
36.         return a106108(n-1) + gcd(n, a106108(n-1))
37.
38. @memoize
39. def a132199(n):
40.     return a106108(n+1) - a106108(n)
41.
42. def a137613(n):
43.     k, nc, a = 1, 1, 5
44.     while nc < n:
45.         k += 1
46.         a = a132199(k)
47.         if a != 1:
48.             nc += 1
49.     return a
50.
51. def lpd(n):
52.     d = 3
53.     while n % d:
54.         d += 2
55.     return d
56.
57. @memoize
58. def shortcut(n):
59.     if n <= 1:
60.         return 5
61.     else:
62.         return lpd(6 - n + sum([shortcut(k) for k in xrange(1, n)]))
63.
64. def tester(a, n):
65.     print "%s:" % a.__name__
66.     tic = time.time()
67.     for k in xrange(1, n + 1):
68.         print a(k),
69.     toc = time.time() - tic
70.     print "\nIt took me %g seconds." % toc
71.
72.
73. if __name__ == '__main__':
74.     for (a, n) in zip([a106108, a132199, a137613, shortcut], [65, 104, 72, 72]):
75.         tester(a, n)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top