Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

rowland.py

By: a guest on Nov 14th, 2010  |  syntax: Python  |  size: 1.58 KB  |  views: 56  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  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)