011: アッカーマンの深淵

ヒント / 解答

難易度: ☆☆

問題

アッカーマン関数 A(m, n) は、非負整数 m と n に対して次のように定義されます。

• m == 0 のとき、A(m, n) = n + 1
• m > 0 かつ n == 0 のとき、A(m, n) = A(m - 1, 1)
• m > 0 かつ n > 0 のとき、A(m, n) = A(m - 1, A(m, n - 1))

m = 3 に固定して、A(3, n) を返す関数 ackermann_3 を書いてください。

制約

• n は0以上10000以下の整数です。
• ackermann_3(10000) を現実的な時間で計算できるようにしてください。

例

>>> ackermann_3(0)
5
>>> ackermann_3(1)
13
>>> ackermann_3(2)
29
>>> ackermann_3(10)
8189

目標

A(3, 10000) は大きい整数です。 値そのものを画面にすべて表示する必要はありません。 まず、次の性質を確認してください。

>>> ackermann_3(10000).bit_length()
10003
>>> len(str(ackermann_3(10000)))
3012

参考

• アッカーマン関数