cp's OEIS Frontend

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

%I A143797 #13 Feb 16 2025 08:33:08
%S A143797 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,
%T A143797 4,2,1,9,9,12,32,65536,65536,4,2,1,10,10,14,64
%N 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).
%C A143797 The next term is 2^^5 = 2^2^2^2^2 = 2^65536.
%C A143797 This is a computable function that is not primitive recursive.
%C A143797 The sequence defined in [Boolos] satisfies B(m,n)=A(m+1,n) for positive m,n.
%D A143797 R. Peter, Rekursive Funktionen in der Komputer-Theorie. Budapest: Akad. Kiado, 1951.
%H A143797 W. Ackermann, <a href="http://eretrandre.org/rb/files/Ackermann1928_126.pdf">Zum Hilbertschen Aufbau der reellen Zahlen</a>, Math. Ann. 99 (1928), 118-133.
%H A143797 G. Boolos, <a href="http://www.jstor.org/stable/30226368">A curious inference</a>, Journal of Philosophical Logic 16 (1987), 1-12.
%H A143797 R. C. Buck, <a href="http://www.jstor.org/stable/2312881">Mathematical induction and recursive definitions</a>, Amer. Math. Monthly, 70 (1963), 128-135.
%H A143797 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/AckermannFunction.html">Ackermann function</a>.
%H A143797 Wikipedia, <a href="http://en.wikipedia.org/wiki/Ackermann_function">Ackermann function</a>.
%F A143797 T(n,0) = 1 if n>=3.
%F A143797 T(n,1) = 2 if n>=2.
%F A143797 T(n,2) = 4 if n>=1.
%F A143797 T(1,n) = 2+n.
%F A143797 T(2,n) = 2*n.
%F A143797 T(3,n) = 2^n.
%F A143797 T(4,n) = 2^^n (a power tower of n two's) = A014221(n+1).
%Y A143797 A001695(n)=A(n, n). Cf. A143796.
%K A143797 nonn,tabl
%O A143797 0,2
%A A143797 _Benoit Jubin_, Sep 01 2008