A143797 Ackermann-Buck function, defined recursively by A(0,n) = n+1, A(1,0) = 2, A(2,0) = 0, A(n+3,0) = 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, 0, 4, 4, 2, 1, 5, 5, 4, 2, 1, 6, 6, 6, 4, 2, 1, 7, 7, 8, 8, 4, 2, 1, 8, 8, 10, 16, 16, 4, 2, 1, 9, 9, 12, 32, 65536, 65536, 4, 2, 1, 10, 10, 14, 64

Offset

0,2

Comments

The next term is 2^^5 = 2^2^2^2^2 = 2^65536.

This is a computable function that is not primitive recursive.

The sequence defined in [Boolos] satisfies B(m,n)=A(m+1,n) for positive m,n.

References

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

Links

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

W. Ackermann, Zum Hilbertschen Aufbau der reellen Zahlen, Math. Ann. 99 (1928), 118-133.

G. Boolos, A curious inference, Journal of Philosophical Logic 16 (1987), 1-12.

R. C. Buck, Mathematical induction and recursive definitions, Amer. Math. Monthly, 70 (1963), 128-135.

Eric Weisstein's World of Mathematics, Ackermann function.

Wikipedia, Ackermann function.

Formula

T(n,0) = 1 if n>=3.

T(n,1) = 2 if n>=2.

T(n,2) = 4 if n>=1.

T(1,n) = 2+n.

T(2,n) = 2*n.

T(3,n) = 2^n.

T(4,n) = 2^^n (a power tower of n two's) = A014221(n+1).

Crossrefs

A001695(n)=A(n, n). Cf. A143796.

Sequence in context: A300290 A068460 A308120 * A319772 A079729 A288723

Adjacent sequences: A143794 A143795 A143796 * A143798 A143799 A143800

Keyword

nonn,tabl

Author

Benoit Jubin, Sep 01 2008

Status

approved