cp's OEIS Frontend

A046859 Simplified Ackermann function (main diagonal of Ackermann-Péter function).

%I A046859 #64 Jul 19 2021 21:19:52
%S A046859 1,3,7,61
%N A046859 Simplified Ackermann function (main diagonal of Ackermann-Péter function).
%C A046859 The next term is 2^(2^(2^(2^16))) - 3, which is too large to display in the DATA lines.
%C A046859 Another version of the Ackermann numbers is the sequence 1^1, 2^^2, 3^^^3, 4^^^^4, 5^^^^^5, ..., which begins 1, 4, 3^3^3^... (where the number of 3's in the tower is 3^3^3 = 7625597484987), ... [Conway and Guy]. This grows too rapidly to have its own entry in the OEIS.
%C A046859 An even more rapidly growing sequence is the Conway-Guy sequence 1, 2->2, 3->3->3, 4->4->4->4, ..., which agrees with the sequence in the previous comment for n <= 3, but then the 4th term is very much larger than 4^^^^4.
%C A046859 From _Natan Arie Consigli_, Apr 10 2016: (Start)
%C A046859 A189896 = succ(0), 1+1, 2*2, 3^3,..., also called Ackermann numbers, is a weaker version of the above sequence.
%C A046859 The Ackermann functions are well-known to be simple examples of computable (implementable using a combination of while/for-loops) but not primitive recursive (implementable using only for-loops) functions.
%C A046859 See A054871 for the definitions of the hyperoperations (a[n]b and H_n(a,b)).
%C A046859 The original Ackermann function f is defined by:
%C A046859 {
%C A046859 {f(0,y,z)=y+z;
%C A046859 {f(1,y,0)=0;
%C A046859 {f(2,y,0)=1;
%C A046859 {f(x,y,0)=x;
%C A046859 {f(x,y,z)=f(x-1,y,f(x,y,z-1))
%C A046859 {
%C A046859 Here we have f(1,y,z)=y*z, f(2,y,z)=y^z.
%C A046859 Ackermann function variants are 3-argument functions that satisfy the recurrence relation above.
%C A046859 Example:
%C A046859 the hyperoperation function H(x,y,z) satisfies the original's recurrence relation but has the following initial values:
%C A046859 {
%C A046859 {H(0,y,z) = y+1;
%C A046859 {H(1,y,0) = y;
%C A046859 {H(2,y,0) = 0;
%C A046859 {H(n,y,0) = 1.
%C A046859 {
%C A046859 The family of Ackermann functions can be simplified by omitting the "y" variable of the 3-argument function by making them have two arguments.
%C A046859 A 2-argument Ackermann function would then be a function satisfying the recurrence relation: f(x,z)=f(x-1,f(x,z-1)).
%C A046859 The most popular example is Ackermann-Péter's function defined by:
%C A046859 {
%C A046859 {A(0,y) = y+1;
%C A046859 {A(x+1,0) = A(x,1);
%C A046859 {A(x+1,y+1) = A(x,A(x+1,y))
%C A046859 {
%C A046859 Here we have A(0,y-1) = y = 2[0](y-1+3)-3.
%C A046859 Suppose A(x-1,y-1) = 2[x-1](y-1+3)-3.
%C A046859 By induction on positive x:
%C A046859 since 2[x]2 = 4 (See A255176) we have A(x,0) = A(x-1,1) = 2[x-1]4-3 = 2[x-1]2[x-1]2-3 = 2[x-1]3-3.
%C A046859 By induction on positive y we can conclude that:
%C A046859 A(x,y) = A(x-1,A(x,y-1)) = 2[x-1](2[x](y-1+3)-3+3)-3 = 2[x-1]2[x](y-1+3)-3 = 2[x](y+3)-3.
%C A046859 *
%C A046859 If f is a 3-argument (2-argument) Ackermann function, Ack(n) = f(n,n,n) (f(n,n)) is called a simplified Ackermann function. The "Ackermann numbers" are the values of Ack(n).
%C A046859 Here we have a(n) = A(n,n) = 2[n](n+3)-3.
%C A046859 (End)
%D A046859 Conway, J. H. and Guy, R. K. The Book of Numbers. New York: Springer-Verlag, p. 60, 1996.
%D A046859 G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.
%D A046859 H. Hermes, Aufzaehlbarkeit, Entscheidbarkeit, Berechenbarkeit: Einfuehrung in die Theorie der rekursiven Funktionen (3rd ed., Springer, 1978), 83-89.
%D A046859 H. Hermes, ditto, 2nd ed. also available in English (Springer, 1969), ch. 13
%H A046859 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 A046859 D. E. Knuth and N. J. A. Sloane, <a href="/A046859/a046859.pdf">Correspondence, May 1970</a>
%H A046859 <a href="/index/Ab#Ackermann">Index entries for sequences related to Ackermann function</a>
%F A046859 From _Natan Arie Consigli_, Apr 10 2016: (Start)
%F A046859 A(0, y) := y+1, A(x+1, 0) := A(x, 1), A(x+1, y+1) := A(x, A(x+1, y));
%F A046859 a(n) = A(n,n).
%F A046859 a(n) = 2[n](n+3)-3 = H_n(2,n+3)-3.  (End)
%e A046859 From _Natan Arie Consigli_, Apr 10 2016: (Start)
%e A046859 a(0) = 2[0](0+3)-3 = 1;
%e A046859 a(1) = 2[1](1+3)-3 = 3;
%e A046859 a(2) = 2[2](2+3)-3 = 7;
%e A046859 a(3) = 2[3](3+3)-3 = 61;
%e A046859 a(4) = 2[4](4+3)-3 = 2^(2^(2^65536)) - 3.  (End)
%Y A046859 Cf. A059936, A266200, A271553. (sequences involving simplified Ackermann Functions)
%Y A046859 Cf. A001695, A014221, A143797, A264929 (sequences involving other versions of two-argument Ackermann's Function).
%Y A046859 Cf. A054871, A189896 (sequences involving variants of the three-argument Ackermann's Function).
%Y A046859 Cf. A126333 (a(n)=A(n,0)), A074877 (a(n)=A(3,n)).
%Y A046859 Cf. A260002-A260006 (sequences with Sudan's function, another computable but not primitive recursive function).
%Y A046859 Cf. A266201 (Goodstein's function, total and not primitive recursive).
%K A046859 nonn,bref
%O A046859 0,2
%A A046859 _Don Knuth_
%E A046859 Additional comments from _Frank Ellermann_, Apr 21 2001
%E A046859 Name clarified by _Natan Arie Consigli_, May 13 2016