アッカーマン関数

一応残しておく.

$ python
Python 2.6.2 (r262:71600, Jun  5 2009, 23:21:35)
[GCC 3.4.4 (cygming special, gdc 0.12, using dmd 0.125)] on cygwin
Type "help", "copyright", "credits" or "license" for more information.
>>> cache = {}
>>>
>>> def memoize(f):
...     global cache
...     def _(*args):
...         if not args in cache:
...             cache[args] = f(*args)
...         return cache[args]
...     return _
...
>>> @memoize
... def ack(m, n):
...     if m == 0:
...         return n + 1
...     elif m == 1:
...         return n + 2
...     elif m == 2:
...         return n * 2 + 3
...     elif m == 3:
...         return 2 ** (n + 3) - 3
...     elif n == 0:
...         return ack(m - 1, 1)
...     else:
...         if not (m, n - 1) in cache:
...             for i in range(n):
...                 ack(m, i)
...         return ack(m - 1, ack(m, n - 1))
...
>>> ack(4, 1)
65533
>>> len(str(ack(4, 2)))
19729