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