cp's OEIS Frontend

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

%I A143796 #8 Feb 16 2025 08:33:08
%S A143796 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
%N 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).
%C A143796 Also known as Ackermann-Peter function.
%C A143796 The next term is 2^65536-3.
%C A143796 This is a computable function that is not primitive recursive.
%D A143796 R. Peter, Rekursive Funktionen in der Komputer-Theorie. Budapest: Akad. Kiado, 1951.
%H A143796 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 A143796 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 A143796 E. Weisstein, Mathworld, <a href="https://mathworld.wolfram.com/AckermannFunction.html">Ackermann function</a>.
%H A143796 Wikipedia, <a href="http://en.wikipedia.org/wiki/Ackermann_function">Ackermann function</a>.
%F A143796 A(1,n) = 2+(n+3) - 3 = n + 2.
%F A143796 A(2,n) = 2*(n+3) - 3 = 2n + 3.
%F A143796 A(3,n) = 2^(n+3) - 3.
%F A143796 A(4,n) = 2^^(n+3)- 3 (a power tower of n+3 two's).
%Y A143796 A046859(n)=A(n, n), A126333(n)=A(n, 0). Cf. A143797.
%K A143796 nonn,tabl
%O A143796 0,2
%A A143796 _Benoit Jubin_, Sep 01 2008