A143796 Ackermann function, defined recursively by A(0,n) = n+1, A(m+1,0) = A(m,1), A(m+1,n+1) = A(m,A(m+1,n)) for any nonnegative integers n, m. Table read by antidiagonals, the second term being A(0,1).

1, 2, 2, 3, 3, 3, 4, 4, 5, 5, 5, 5, 7, 13, 13, 6, 6, 9, 29, 65533, 65533, 7, 7, 11, 61

Offset: 0

Author

Benoit Jubin, Sep 01 2008

Keywords

• nonn
• tabl

Comments

Also known as Ackermann-Peter function.

The next term is 2^65536-3.

This is a computable function that is not primitive recursive.

References

• R. Peter, Rekursive Funktionen in der Komputer-Theorie. Budapest: Akad. Kiado, 1951.

Links

• W. Ackermann, Zum Hilbertschen Aufbau der reellen Zahlen, Math. Ann. 99 (1928), 118-133.
• R. C. Buck, Mathematical induction and recursive definitions, Amer. Math. Monthly, 70 (1963), 128-135.
• E. Weisstein, Mathworld, Ackermann function.
• Wikipedia, Ackermann function.

Crossrefs

A046859(n)=A(n, n), A126333(n)=A(n, 0). Cf. A143797.

Formula

A(1,n) = 2+(n+3) - 3 = n + 2.

A(2,n) = 2*(n+3) - 3 = 2n + 3.

A(3,n) = 2^(n+3) - 3.

A(4,n) = 2^^(n+3)- 3 (a power tower of n+3 two's).