rowland.py

#!/usr/bin/env python2.6
"""
rowland.py
See http://programmingpraxis.com/2010/11/12/rowlands-prime-generating-function/

We make heavy use of memoization in order to trade space for time whenever we
define a recursive function or a function that is used by another.

GRE, 11/14/10
"""

import time
import functools

def gcd(a, b):
   while b:
       a, b = b, a % b
   return a

def memoize(func):
    func.memo = {}
    def memoizer(arg):
        try:
# Try using the memo dict, or else update it
            return func.memo[arg]
        except KeyError:
            func.memo[arg] = result = func(arg)
            return result
    return functools.update_wrapper(memoizer, func)

@memoize
def a106108(n):
    if n == 1:
        return 7
    else:
        return a106108(n-1) + gcd(n, a106108(n-1))

@memoize
def a132199(n):
    return a106108(n+1) - a106108(n)

def a137613(n):
    k, nc, a = 1, 1, 5
    while nc < n:
        k += 1
        a = a132199(k)
        if a != 1:
            nc += 1
    return a

def lpd(n):
    d = 3
    while n % d:
        d += 2
    return d

@memoize
def shortcut(n):
    if n <= 1:
        return 5
    else:
        return lpd(6 - n + sum([shortcut(k) for k in xrange(1, n)]))

def tester(a, n):
    print "%s:" % a.__name__
    tic = time.time()
    for k in xrange(1, n + 1):
        print a(k),
    toc = time.time() - tic
    print "\nIt took me %g seconds." % toc


if __name__ == '__main__':
    for (a, n) in zip([a106108, a132199, a137613, shortcut], [65, 104, 72, 72]):
        tester(a, n)