login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

Table of n, a(n) for n=0..3.

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

Don Knuth

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 18 11:56 EDT 2018. Contains 316321 sequences. (Running on oeis4.)