Background

Description

函数-阿克曼函数（Ackermann），并计算其循环次数

在递归函数论和涉及集合的并的某些算法的复杂性研究中，有一个起重要作用的递归函数——阿克曼（Ackermann）函数,该函数是由希尔伯特的学生，德国著名数学家威尔海姆·阿克曼于1928年发现的。这是一个图灵机可计算的，但不是原始递归的函数。下面，我们介绍这个经典的递归函数，并给出其相应的计算过程。

在可计算性理论中，以 Wilhelm Ackermann 命名的阿克曼函数是非原始递归的总可计算函数的最简单和最早发现的示例之一。 所有原始递归函数都是全函数和可计算的，但阿克曼函数说明并非所有可计算全函数都是原始递归函数。 在阿克曼发表他的函数（具有三个非负整数参数）之后，许多作者对其进行了修改以适应各种目的，因此今天的阿克曼函数可能指的是原始函数的众多变体中的任何一个。

在 20 年代后期，大卫希尔伯特的学生数学家加布里埃尔苏丹和威廉阿克曼正在研究计算的基础。 Sudan 和 Ackermann 都因发现了非原始递归的总可计算函数（在某些参考文献中简称为递归）而受到赞誉。 苏丹发表了鲜为人知的苏丹函数，不久之后，阿克曼在 1928 年独立发表了他的函数 φ {displaystyle varphi }（希腊字母 phi）。

（除了其作为完全可计算但非原始递归函数的历史角色外，阿克曼的原始函数被视为将基本算术运算扩展到求幂之外，尽管不如阿克曼的变体那样无缝 专门为此目的设计的函数——例如 Goodstein 的超操作序列。）

在 On the Infinite 中，David Hilbert 假设阿克曼函数不是原始递归，但实际上是 Hilbert 的私人秘书兼前学生 Ackermann 在他的论文 On Hilbert's Construction of the 实数。

Rózsa Péter 和 Raphael Robinson 后来开发了一个双变量版本的阿克曼函数，几乎成为所有作者的首选。

广义超操作序列，例如 G ( m , a , b ) = a [ m ] b {displaystyle G(m,a,b)=a[m]b} ，也是阿克曼函数的一个版本。

Format

Input

Output

Samples

4
1

ncount=3561
533

999
999

ncount=10000
ncount=20000
ncount=30000
ncount=40000
ncount=50000
ncount=60000
ncount=70000
ncount=80000
ncount=90000
ncount=100000
ncount=110000
ncount=120000
ncount=130000
ncount=140000
ncount=150000
ncount=160000
ncount=170000
ncount=180000
ncount=190000
ncount=200000
ncount=210000
ncount=220000
ncount=230000
ncount=240000
ncount=250000
ncount=260000
ncount=270000
ncount=280000
ncount=290000
ncount=300000
ncount=310000
ncount=320000
ncount=330000
ncount=340000
ncount=350000
ncount=360000
ncount=370000
ncount=380000
ncount=390000
ncount=400000
ncount=410000
ncount=420000
ncount=430000
ncount=440000
ncount=450000
ncount=460000
ncount=470000
ncount=480000
ncount=490000
ncount=500000
ncount=510000
ncount=520000
ncount=530000
ncount=540000
ncount=550000
ncount=560000
ncount=570000
ncount=580000
ncount=590000
ncount=600000
ncount=610000
ncount=620000
ncount=630000
ncount=640000
ncount=650000
ncount=660000
ncount=670000
ncount=680000
ncount=690000
ncount=700000
ncount=710000
ncount=720000
ncount=730000
ncount=740000
ncount=750000
ncount=760000
ncount=770000
ncount=780000
ncount=790000
ncount=800000
ncount=810000
ncount=820000
ncount=830000
ncount=840000
ncount=850000
ncount=860000
ncount=870000
ncount=880000
ncount=890000
ncount=900000
ncount=910000
ncount=920000
ncount=930000
ncount=940000
ncount=950000
ncount=960000
ncount=970000
ncount=980000
ncount=990000
ncount=1000000
ncount=1010000
ncount=1020000
ncount=1030000
ncount=1040000
ncount=1050000
ncount=1060000
ncount=1070000
ncount=1080000
ncount=1090000
ncount=1100000
ncount=1110000
ncount=1120000
ncount=1130000
ncount=1140000
ncount=1150000
ncount=1160000
ncount=1170000
ncount=1180000
ncount=1190000
ncount=1200000
ncount=1210000
ncount=1220000
ncount=1230000
ncount=1240000
ncount=1250000
ncount=1260000
ncount=1270000
ncount=1280000
ncount=1290000
ncount=1300000
ncount=1310000
ncount=1320000
ncount=1330000
ncount=1340000
ncount=1350000
ncount=1360000
ncount=1370000
ncount=1380000
ncount=1390000
ncount=1400000
ncount=1410000
ncount=1420000
ncount=1430000
ncount=1440000
ncount=1450000
ncount=1460000
ncount=1467110
733

Limitation

1s, 1024KiB for each test case.