The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A046859 Simplified Ackermann function (main diagonal of Ackermann-Péter function). 8
 1, 3, 7, 61 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,2 COMMENTS The next term is 2^(2^(2^(2^16))) - 3, which is too large to display in the DATA lines. 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. 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. From Natan Arie Consigli, Apr 10 2016: (Start) A189896(n) = succ(0), 1+1, 2*2, 3^3,..., also called Ackermann numbers, is a weaker version of the above sequence. 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 a FINITE number of do-while/for-loops) functions. See A054871 for the definitions of the hyperoperations (a[n]b and H_n(a,b)). The original Ackermann function f is defined by: { {f(0,y,z)=y+z; {f(1,y,0)=0; {f(2,y,0)=1; {f(x,y,0)=x; {f(x,y,z)=f(x-1,y,f(x,y,z-1)) { Here we have f(1,y,z)=y*z, f(2,y,z)=y^z. Ackermann function variants are 3-argument functions that satisfy the recurrence relation above. Example: the hyperoperation function H(x,y,z) satisfies the original's recurrence relation but has the following initial values: { {H(0,y,z) = y+1; {H(1,y,0) = y; {H(2,y,0) = 0; {H(n,y,0) = 1. { The family of Ackermann functions can be simplified by omitting the "y" variable of the 3-argument function by making them have two arguments. A 2-argument Ackermann function would then be a function satisfying the recurrence relation: f(x,z)=f(x-1,f(x,z-1)). The most popular example is Ackermann-Péter's function defined by: { {A(0,y) = y+1; {A(x+1,0) = A(x,1); {A(x+1,y+1) = A(x,A(x+1,y)) { Here we have A(0,y-1) = y = 2[0](y-1+3)-3. Suppose A(x-1,y-1) = 2[x-1](y-1+3)-3. By induction on positive x: 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. By induction on positive y we can conclude that: 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. * 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). Here we have a(n) = A(n,n) = 2[n](n+3)-3. (End) REFERENCES Conway, J. H. and Guy, R. K. The Book of Numbers. New York: Springer-Verlag, p. 60, 1996. G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255. H. Hermes, Aufzaehlbarkeit, Entscheidbarkeit, Berechenbarkeit: Einfuehrung in die Theorie der rekursiven Funktionen (3rd ed., Springer, 1978), 83-89. H. Hermes, ditto, 2nd ed. also available in English (Springer, 1969), ch. 13 LINKS W. Ackermann, Zum Hilbertschen Aufbau der reellen Zahlen, Math. Ann. 99 (1928), 118-133. D. E. Knuth and N. J. A. Sloane, Correspondence, May 1970 FORMULA From Natan Arie Consigli, Apr 10 2016: (Start) A(0, y) := y+1, A(x+1, 0) := A(x, 1), A(x+1, y+1) := A(x, A(x+1, y)); a(n) = A(n,n). a(n) = 2[n](n+3)-3 = H_n(2,n+3)-3.  (End) EXAMPLE From Natan Arie Consigli, Apr 10 2016: (Start) a(0) = 2[0](0+3)-3 = 1; a(1) = 2[1](1+3)-3 = 3; a(2) = 2[2](2+3)-3 = 7; a(3) = 2[3](3+3)-3 = 61; a(4) = 2[4](4+3)-3 = 2^(2^(2^65536)) - 3.  (End) CROSSREFS Cf. A059936, A266200, A271553. (sequences involving simplified Ackermann Functions) Cf. A001695, A014221, A143797, A264929 (sequences involving other versions of two-argument Ackermann's Function). Cf. A054871, A189896 (sequences involving variants of the three-argument Ackermann's Function). Cf. A126333 (a(n)=A(n,0)), A074877 (a(n)=A(3,n)). Cf. A260002-A260006 (sequences with Sudan's function, another computable but not primitive recursive function). Cf. A266201 (Goodstein's function, total and not primitive recursive). Sequence in context: A185846 A239023 A164895 * A242380 A225195 A084289 Adjacent sequences:  A046856 A046857 A046858 * A046860 A046861 A046862 KEYWORD nonn,bref AUTHOR EXTENSIONS Additional comments from Frank Ellermann, Apr 21 2001 Name clarified by Natan Arie Consigli, May 13 2016 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified June 7 05:20 EDT 2020. Contains 334837 sequences. (Running on oeis4.)