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,2

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

Table of n, a(n) for n=0..24.

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.

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).

Crossrefs

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

Sequence in context: A274533 A163127 A077113 * A245473 A306904 A371627

Adjacent sequences: A143793 A143794 A143795 * A143797 A143798 A143799

Keyword

nonn,tabl

Author

Benoit Jubin, Sep 01 2008

Status

approved