A189896 -id:A189896 - cp's OEIS frontend

A213619 Let m be the n-th hyperoperation applied to n (see A189896). a(n) is the m-th hyperoperation applied to n and m.

1, 2, 65536

Offset: 0

Jens Ahlström, Jun 16 2012

Let bn=A189896(n), that is, bn=H_n(n,n), where H_n is the n-th hyperoperation.
Then
a(n) = H_bn(n,bn), hence
a(0) = H_b0(0,b0) = H_1(0,1) = 0+1 = 1,
a(1) = H_b1(1,b1) = H_2(1,2) = 1*2 = 2,
a(2) = H_b2(2,b2) = H_4(2,4) = 2^2^2^2 = 65536, and
a(3) is too large to include here.

			a(0) = H_H_0(0,0)(0,H_0(0,0)) = H_1(0,1) = 0+1 = 1.
a(1) = H_H_1(1,1)(1,H_1(1,1)) = H_2(1,1+1) = 1*(1+1) = 2.
a(2) = H_H_2(2,2)(2,H_2(2,2)) = H_4(2,2*2) = H_3(2,H_3(2,H_3(2,2))) = 2^2^2^2 = 2^2^4 = 2^16 = 65536.

Cf. A189896.

a(n) = H_H_n(n,n)(n,H_n(n,n)).

A054871 a(n) = H_n(3,2) where H_n is the n-th hyperoperator.

Original entry on oeis.org

3, 5, 6, 9, 27, 7625597484987

Offset: 0

Walter Nissen, May 28 2000

nonn

H_n(x,y) is defined recursively by:
  H_0(x,y) = y+1;
  H_1(x,0) = x;
  H_2(x,0) = 0;
  H_n(x,0) = 1, for n>2;
  H_n(x,y) = H_{n-1}(x,H_n(x,y-1)), for integers n>0 and y>0.
Consequently:
  H_0(x,y) = y+1  is the successor function on y;
  H_1(x,y) = x+y  is addition;
  H_2(x,y) = x*y  is multiplication;
  H_3(x,y) = x^y  is exponentiation;
  H_4(x,y) = x^^y is tetration (a height-y exponential tower x^x^x^... );
  ...
Extending to negative-order hyperoperators via the recursive formula:
  H_0(x,y) = H_{-1}(x,H_0(x,y-1)) = H_{-1}(x,y).
Therefore:
  H_{-n}(x,y) = H_0(x,y), for every nonnegative n.
This function is an Ackermann function variant because it satisfies the recurrence relation above (see A046859).
Other hyperoperation notations equivalent to H_n(x,y) include:
Square Bracket or Box: a [n] b;
Conway Chain Arrows: a -> b -> n-2;
Knuth Up-arrow: a "up-arrow"(n-2) b;
Standard Caret: a ^(n-2) b.
Originally published as 3 agg-op-n 3 for n > 0. - Natan Arie Consigli, Apr 22 2015
Sequence can also be defined as a(0) = 3, a(1) = 5, a(n) = H_{n-1}(3,3) for n > 1. - Natan Arie Consigli, Apr 22 2015; edited by Danny Rorabaugh, Oct 18 2015
Before introducing the H_n notation, this sequence was named "3 agg-op-n 2, where the binary aggregation operators agg-op-n are zeration, addition, multiplication, exponentiation, superexponentiation, ..." - Danny Rorabaugh, Oct 14 2015
The next term is 3^3^...^3 (with 7625594784987 3's). - Jianing Song, Dec 25 2018

			a(0) = H_0(3,2) = 2+1 = 3;
a(1) = H_1(3,2) = 3+2 = 5;
a(2) = H_2(3,2) = 3*2   = 3+3  = 6;
a(3) = H_3(3,2) = 3^2   = 3*3  = 9;
a(4) = H_4(3,2) = 3^^2  = 3^3  = 27;
a(5) = H_5(3,2) = 3^^^2 = 3^^3 = 3^(3^3) = 7625597484987.

John H. Conway and R. K. Guy, The Book of Numbers, Copernicus Press, p. 60.

Rick Norwood, Math. Bite: Why 2 + 2 = 2 * 2, Mathematics Magazine, Vol. 71 (1998), p. 60.
Stephen R. Wassell, Superexponentiation and Fixed Points of Exponential and Logarithmic Functions, Mathematics Magazine, Vol. 73 (2000), pp. 111-119.
Eric Weisstein's MathWorld, Ackermann Function and Power Tower
Wikipedia, Hyperoperation
Index Section Ho-Hy

H_n(x,y) for various x,y: A001695 (2,n), this sequence (3,2; almost 3,3), A067652 (2,3; almost 2,4), A141044 (1,1), A175796 (n,2), A179184 (0,0), A189896 (n,n), A213619 (n,H_n(n,n)), A253855 (4,2; almost 4,4), A255176 (2,2),  A255340 (4,3), A256131 (10,2; almost 10,10), A261143 (1,2), A261146 (n,3). - Natan Arie Consigli and Danny Rorabaugh, Oct 14-26 2015
H_4(x,n) for various x: A000035 (x=0), A014221 (x=2), A014222 (x=3, shifted), A057427 (x=1).
H_5(x,n) for various x: A266198 (x=2), A266199 (x=3).
Cf. A254225, A254310, A257229.

First two terms prepended by Natan Arie Consigli, Apr 22 2015
First term corrected and hyperoperator notation implemented by Danny Rorabaugh, Oct 14 2015
Definition extended to include negative n by Natan Arie Consigli, Oct 19 2015
More hyperoperator notation added by Natan Arie Consigli, Jan 19 2016

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

Original entry on oeis.org

1, 3, 7, 61

Offset: 0

Don Knuth

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

			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)

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

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
Index entries for sequences related to Ackermann function

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

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)

Additional comments from Frank Ellermann, Apr 21 2001

Name clarified by Natan Arie Consigli, May 13 2016

A260002 Sudan Numbers: a(n)= f(n,n,n) where f is the Sudan function.

Original entry on oeis.org

0, 3, 15569256417

Offset: 0

Natan Arie Consigli, Jul 12 2015

The Sudan function is the first discovered not primitive recursive function that is still totally recursive like the well-known three-argument (or two-argument) Ackermann function ack(a,b,c) (or ack(a,b)).
The Sudan function is defined as follows:
f(0,x,y) = x+y;
f(z,x,0) = x;
f(z,x,y) = f(z-1, f(z,x,y-1), f(z,x,y-1)+y).
Just as the three-argument (or two-argument) Ackermann numbers A189896 (or A046859) are defined to be the numbers that are the answer of ack(n,n,n) (or ack(n,n)) for some natural number n, the Sudan numbers are: a(n) = f(n,n,n).
a(3)> 2^(76*2^(76*2^(76*2^(76*2^76)))) so is too big to be included.

			a(1) = f(1,1,1) = f(0, f(1,1,0), f(1,1,0)+1) = f(0, 1, 2) = 1+2 = 3.

Wikipedia, Sudan Function, Primitive Recursive, Ackermann function.

Cf. A189896, A046859, A260003, A260004, A260005, A260006.

f[z_, x_, y_] := f[z, x, y] =
Piecewise[{{x + y, z == 0}, {x,
    z > 0 && y == 0}, {f[z - 1, f[z, x, y - 1], f[z, x, y - 1] + y],
    z > 0 && y > 0} }];
a[n_] := f[n,n,n]

f(z,x,y)=if(z,if(y,my(t=f(z,x,y-1)); f(z-1, t, t+y),x),x+y)
a(n)=f(n,n,n) \\ Charles R Greathouse IV, Jul 28 2015

A271553 a(n) = H_{n-1}(n,n).

Original entry on oeis.org

1, 2, 4, 9, 64

Offset: 0

Natan Arie Consigli, Apr 09 2016

H is the hyperoperation function see A054871 for more information.

This sequence is a shifted version of the weak Ackermann numbers H_n(n,n).

Cf. A189896 (H_n(n,n)), A054871.

A264930 a(n) = nn where xy is a right associative hyperoperation.

Original entry on oeis.org

1, 2, 4, 27, 340282366920938463463374607431768211456

Offset: 0

Natan Arie Consigli, Nov 29 2015

nonn

Define xy recursively as follows (this is a right associative version):
x<0>y = x+1;
x<1>0 = x;
x<2>0 = 0;
xy = ( x(y-1) )  x for n>0 and y>0.
We have:
x<1>y = (...((x<0>y)<0>y)...y)(y nested parenthesis) = x+y;
x<2>y = (...((x<1>y)<1>y)...y)(y nested parenthesis) = x*y;
x<3>y = (...((x<2>y)<2>y)...y)(y nested parenthesis)  = x^y;
x<4>y = (...((x<3>y)<3>y)...y)(y nested parenthesis) = (...((x^x)^x)...^x) (a height-y bottom-up tower power, NOT tetration) = x^x^(y-1).
...

			a(0) = 0+1 = 1;
a(1) = 1+1 = 2;
a(2) = 2*2 = 4;
a(3) = 3^3 = 27;
a(4) = ((4^4)^4)^4 = 340282366920938463463374607431768211456;
a(5) = 5<5>5 = (((((5<4>5)<4>5)<4>5)<4>5)<4>5)<4>5.

Wikipedia, Hyperoperations.

Cf. A054871, A189896.

A375730 a(n) = n^n + n*n + n+n + 1.

Original entry on oeis.org

2, 5, 13, 43, 281, 3161, 46705, 823607, 16777297, 387420589, 10000000121, 285311670755, 8916100448425, 302875106592449, 11112006825558241, 437893890380859631, 18446744073709551905, 827240261886336764501, 39346408075296537575785, 1978419655660313589124379

Offset: 0

Anthony Veglia, Aug 25 2024

The sum of "n OP n" for hyper-operators 0 to 3, where 0 = succession, 1 = addition, 2 = multiplication, 3 = exponentiation.

			a(0) = (0^0)+(0*0)+(0+0)+1 = 1+0+0+1 = 2.
a(3) = (3^3)+(3*3)+(3+3)+1 = 27+9+6+1 = 43.

Cf. A000012, A000290, A000312, A005843, A189896.

Join[{2},Table[n^n+(n+1)^2,{n,19}]] (* James C. McMahon, Sep 13 2024 *)

def A375730(n): return n*(n*(n**(n-2)+1)+2)+1 if n>1 else 3*n+2 # Chai Wah Wu, Sep 02 2024

a(n) = n^n + (n+1)^2.
a(n) = A000312(n) + A000290(n) + A005843(n) + A000012(n).
E.g.f.: (1+3*x+x^2)*exp(x)+1/(1+LambertW(-x)). - Alois P. Heinz, Aug 26 2024

a(19) corrected by James C. McMahon, Sep 13 2024

A275203 Hyperoperations using consecutive integers.

Original entry on oeis.org

1, 2, 4, 64

Offset: 0

Tyler Skywalker, Jul 19 2016

nonn

a(4) is too large to display. The number of decimal digits in (the number of decimal digits in a(4)) is approximately 64^64*log[10](64), that is, about 7.1*10^115. - Robert Israel, Jul 19 2016

			a(0) = H_0(null,0) = 0+1 = 1.
a(1) = H_1(1,1) = 1+1 = 2.
a(2) = H_2(2,2) = 2*2 = 4.
a(3) = H_3(4,3) = 4^3 = 64.
a(4) = H_4(64,4) = 64^(64^(64^64)).

Wikipedia, Hyperoperation

Cf. A189896, A264930.

a(n) = H_n(a(n-1),n), where H_n is the n-th hyperoperation.

A302349 a(n) = F_n(n,n), where F is the Clenshaw-Olver hyper-operation hierarchy.

Original entry on oeis.org

1, 2, 4, 9, 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096

Offset: 0

Natan Arie Consigli, Apr 05 2018

nonn

a(5) is too big to include.
The Clenshaw Olver hyper-operation is a recursive function defined as follows:
F_0(a,b) = b+1
F_n(a,0) = 0
F_n+1(a,b+1) = F_n(a, F_n+1(a, b)), for every nonnegative b and n.

			F_0(0,0) = 0+1 = 1;
F_1(1,1) = 1+1 = 2;
F_2(2,2) = 2*2 = 4;
F_3(a,b) = 3^3 = 9;
F_4(a,b) = 4[4](4-1) = 4^4^4 = ...

C. W. Clenshaw and F. W. J. Olver, Beyond floating point, Journal of the ACM. 31 (2) April 1984, pp. 319-328.

Cf. A054871, A189896 (same instance using traditional hyper-operation hierarchy).

F_1(a,b) = a+b;
F_2(a,b) = ab;
F_3(a,b) = a^b;
F_4(a,b) = a[4](b-1).
a[n]b is the square bracket notation for hyper-operation. See A054871 for details.

cp's OEIS Frontend

A213619 Let m be the n-th hyperoperation applied to n (see A189896). a(n) is the m-th hyperoperation applied to n and m.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A054871 a(n) = H_n(3,2) where H_n is the n-th hyperoperator.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A260002 Sudan Numbers: a(n)= f(n,n,n) where f is the Sudan function.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A271553 a(n) = H_{n-1}(n,n).

Views

Author

Keywords

Comments

Crossrefs

A264930 a(n) = nn where xy is a right associative hyperoperation.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A375730 a(n) = n^n + n*n + n+n + 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A275203 Hyperoperations using consecutive integers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A302349 a(n) = F_n(n,n), where F is the Clenshaw-Olver hyper-operation hierarchy.

Views

Author

Keywords