H(n) -> n - H(H(H(n-1))) として H(2015) を求める

h.py

# coding:utf-8

import functools
import time

# 関数をメモ化します
# すべての引数はハッシュ可能でなければなりません
def memoize(f):
    memo = {} # キャッシュ
    @functools.wraps(f) # 関数fのメタ情報（定義名やパラメタなど）を関数gに引き継ぐ
    def g(*args, **kws):
        key = (tuple(args), tuple(sorted(kws.items(), key=lambda(k,v):k)))
        # 可変長引数(argsとkws)をタプルにエンコード
        if key in memo:
            return memo[key] # Hit 
        value = f(*args, **kws) # Miss
        memo[key] = value
        return value
    return g

# H(0) -> 0
# H(n) -> n - H(H(H(n-1)))
#   where (0 < n)
@memoize #メモ化関数でラップ
def H(n):
    if n == 0:
        return 0
    return n - H(H(H(n-1)))

# エントリポイント
if __name__=="__main__":
    t0 = time.time()
    for n in xrange(0,2015,100): # 0から100づつ2014まで
        H(n) # 一度に計算するとスタックが溢れるので100づつ増やしてキャッシュに載せる
    print("H({0}) -> {1}".format(2015, H(2015)))
    print("done. {0:.4f} [sec]".format(time.time() - t0))