A255176 -id:A255176 - cp's OEIS frontend

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

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

A189896 Weak Ackermann numbers: H_n(n,n) where H_n is the n-th hyperoperator.

Original entry on oeis.org

1, 2, 4, 27

Offset: 0

Max Sills, Apr 30 2011

The next term, a(4), has about 8*10^153 decimal digits. - Charles R Greathouse IV, Nov 15 2022

			a(0) = succ(0) = 0 + 1 = 1, because the zeroth hyperoperation is successor.
a(1) = 1 + 1 = 2, because the first hyperoperation is addition.
a(2) = 2 * 2 = 4, because the second hyperoperation is multiplication.
a(3) = 3^3 = 27, because the third hyperoperation is exponentiation.
a(4) = 4^4^4^4 = 4^(4^(4^4)) = 4^(4^256), because the fourth hyperoperation is tetration. The term is too big to be included: log_2(a(4)) = 2^513.

M. H. Löb and S. S. Wainer, Hierarchies of number-theoretic functions. I, Archive for Mathematical Logic 13:1-2 (1970), pp. 39-51.
Wikipedia, Hyperoperation.
Wikipedia, Ackermann function

For H_n(x,x) with fixed x, cf. A054871 (x=3, shifted), A141044 (x=1), A253855 (x=4, shifted), A255176 (x=2), A256131 (x=10, shifted). - Danny Rorabaugh, Oct 20 2015

Cf. A271553 ( H_n-1(n,n) ). - Natan Arie Consigli, Apr 10 2016

a(n) = H_n(n, n), where H_n the hyperoperation indexed by n.

"Weak" added to definition by Natan Arie Consigli, Apr 18 2015

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

A175796 H_n(n, 2) where H_c(a, b) is the hyperoperation function with operator c.

Original entry on oeis.org

3, 3, 4, 9, 256

Offset: 0

Grant Garcia, Sep 06 2010

nonn

			a(0) = H_0(0, 2) = 2 + 1 = 3
a(1) = H_1(1, 2) = 1 + 2 = 3
a(2) = H_2(2, 2) = 2 * 2 = 4
a(3) = H_3(3, 2) = 3 ^ 2 = 9
a(4) = H_4(4, 2) = 4 ^^ 2 = 4 ^ 4 = 256
a(5) = H_5(5, 2) = 5 ^^^ 2 = 5 ^^ 5 = 5 ^ 5 ^ 5 ^ 5 ^ 5 =~ 10 ^ (10 ^ (10 ^ (2184.1257...)))

Wikipedia, Hyperoperation
Index Section Ho-Hy

For H_n(x,2) with fixed x, cf. A054871 (x=3), A253855 (x=4), A255176 (x=2), A256131 (x=10), A261143 (x=1). - Danny Rorabaugh, Oct 20 2015

def H(a, b, c):
    if c == 0: return b + 1
    if c == 1 and b == 0: return a
    if c == 2 and b == 0: return 0
    if c >= 3 and b == 0: return 1
    return H(a, H(a, b - 1, c), c - 1)
for n in range(5): print(H(n, 2, n))

a(n) = H_n(n, 2)

H_c(a, b) = {b + 1 if c = 0; a if c = 1, b = 0; 0 if c = 2, b = 0; 1 if c >= 3, b = 0; H_{c-1}(a, H_c(a, b - 1)) otherwise}

A267649 a(0) = a(1) = 2 then a(n) = 4 for n>=2.

Original entry on oeis.org

2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4

Offset: 0

Natan Arie Consigli, Jan 19 2016

Decimal expansion of 101/450.
Also list of smallest n-composites.
A hyperoperator aggregation b[n]c is n-composite if b,c are positive non-right-identity elements.
The identity elements are:
Hyper-0 (zeration): none.
Hyper-1 (addition): 0.
Hyper-2 (multiplication): 1.
Hyper-3 (exponentiation): 1.
Hyper-n (n>2): 1.
For more information on hyperoperations see A054871.
Essentially the same as A255176, A151798, A123932, A113311, A040002 and A010709. - R. J. Mathar, May 25 2023
Continued fraction expansion of 2 + sqrt(1/5) = 2 + sqrt(5)/5. - Elmo R. Oliveira, Aug 06 2024

			a(0) = 2 because 1 is the smallest non-identity element in zeration and 1[0]1=2;
a(1) = 2 because 1 is the smallest non-identity element in addition and 1[1]1=2;
a(2) = 4 because 2 is the smallest non-identity element in multiplication and 2[2]2=4;
a(3) = 4 because 2 is the smallest non-identity element in exponentiation and 2[2]2=4;
a(4) = 4 because 2 is the smallest non-identity element in titration and 2[2]2=4;
Etc.

Index entries for linear recurrences with constant coefficients, signature (1).

Cf. A000027 (1-composites), A002808 (composites), A267647 (3-composites), A097374 (4-composites).

a(n) = a[n]b where a,b are the positive smallest non-right-identity elements.
From Elmo R. Oliveira, Aug 06 2024: (Start)
G.f.: 4/(1 - x) - 2*(1 + x).
E.g.f.: 4*exp(x) - 2*(1 + x). (End)

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A189896 Weak Ackermann numbers: H_n(n,n) where H_n is the n-th hyperoperator.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A175796 H_n(n, 2) where H_c(a, b) is the hyperoperation function with operator c.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

Formula

A267649 a(0) = a(1) = 2 then a(n) = 4 for n>=2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula