A260006 -id:A260006 - cp's OEIS frontend

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

1, 3, 7, 61

Offset: 0

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

A052749 a(n) = 2n Stirling2(n-1,2).

Original entry on oeis.org

0, 0, 0, 6, 24, 70, 180, 434, 1008, 2286, 5100, 11242, 24552, 53222, 114660, 245730, 524256, 1114078, 2359260, 4980698, 10485720, 22020054, 46137300, 96468946, 201326544, 419430350, 872415180, 1811939274, 3758096328, 7784628166, 16106127300, 33285996482

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

a(n) is the number of ordered set partitions of an n-set into 3 nonempty sets such that the first set contains exactly one element. a(5) = 70 since the ordered set partitions are the following: 20 of type {1},{2,3,4},{5}; 30 of type {1},{2,3},{4,5}; 20 of type {1},{2},{3,4,5}. - Enrique Navarrete, Jun 11 2023

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 705
Index entries for linear recurrences with constant coefficients, signature (6,-13,12,-4).

Cf. A008277, A000918, A260006.

[n le 2 select 0 else n*(2^(n-1)-2): n in [0..40]]; // Vincenzo Librandi, Nov 18 2014

spec := [S,{B=Set(Z,1 <= card),S=Prod(Z,B,B)},labeled]: seq(combstruct[count](spec,size=n), n=0..20);
g := taylor(exp(x)^2*x-2*x*exp(x)+x,x=0,121): q := seq(coeff(g,x,i)*i!,i=0..120);

Table[If[n < 3, 0, (n*(2^n - 3) - n)/2], {n, 0, 200}] (* Vladimir Joseph Stephan Orlovsky, Jun 30 2011 *)
LinearRecurrence[{6,-13,12,-4},{0,0,0,6,24,70},40] (* Harvey P. Dale, Aug 30 2017 *)

E.g.f.: x*exp(x)^2 - 2*x*exp(x) + x.
Recurrence: {a(1)=0, a(2)=0, a(3)=6, (2*n^2+6*n+4)*a(n)+(-6*n-3*n^2)*a(n+1)+(n^2+n)*a(n+2)}.
a(n) = Sum_{k=3..n} n*2^(k-2). - Zerinvary Lajos, Oct 09 2006
a(n) = n*(2^(n-1)-2) = n*A000918(n-1), n >= 3. - Mitch Harris, Oct 25 2006
O.g.f.: 2*x^3*(3-6*x+2*x^2)/((-1+x)^2*(-1+2*x)^2). - R. J. Mathar, Dec 05 2007
a(n) = Sum_{j=1..n} ( Sum_{i=2..n-1} (j+1)*2^(j-i-1) ). - Wesley Ivan Hurt, Nov 17 2014
a(n) = n*(2^n-4)/2, n > 1. - Wesley Ivan Hurt, Nov 17 2014
a(n) = 2*A260006(n-2). - R. J. Mathar, Apr 26 2017

Better description from Victor Adamchik (adamchik(AT)cs.cmu.edu), Jul 19 2001

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

A260005 a(n) = f(2,n,2), where f is the Sudan function defined in A260002.

Original entry on oeis.org

19, 10228, 15569256417, 5742397643169488579854258, 36681813266165915713665394441869800619098139628586701684547

Offset: 0

Natan Arie Consigli, Jul 23 2015

nonn

Naturally a subsequence of A260004.
See A260002-A260003 for the evaluation of the Sudan function.
Using f(2,n,2) = f(1, f(2,n,1), f(2,n,1)+2) = 2^(f(2,n,1)+2)*(f(2,n,1)+2)-f(2,n,1)-4 and f(2,n,1) = f(1, n, n+1) = 2^(n+1)*(n+2)-(n+3) we have:
a(n)=f(2,n,2)
    =f(1, 2^(n+1)*(n+2)-(n+3), 2^(n+1)*(n+2)-(n+3)+2)
    =2^(2^(n+1)*(n+2)-(n+3)+2)*(2^(n+1)*(n+2)-(n+3)+2)-2^(n+1)*(n+2)+(n+3)-4
    =2^(2^(n+1)*(n+2)-(n+1))*(2^(n+1)*(n+2)-(n+1))-2^(n+1)*(n+2)+(n-1).

			a(1) = f(2,1,2) = f(1,f(2,1,1),f(2,1,1)+2) = f(1,8,10) = 2^10*(8+2)-10-2 = 10228.

Natan Arie' Consigli, Table of n, a(n) for n = 0..6
Wikipedia, Sudan function (see 3rd line of "Values of F2(x, y)" table).

Cf. A048493 (f(2,n,1)), A260002, A260003, A260004, A260006.

[2^(2^(n+1)*(n+2)-(n+1))*(2^(n+1)*(n+2)-(n+1))-2^(n+1)*(n+2)+(n-1):n in [0..5]]; // Vincenzo Librandi, Jul 27 2015

Table[2^(2^(n + 1) (n + 2) - (n + 1)) (2^(n + 1) (n + 2) - (n + 1)) - 2^(n + 1) (n + 2) + (n - 1), {n, 0, 5}] (* Vincenzo Librandi, Jul 27 2015 *)

a(n) = 2^(2^(n+1)*(n+2)-(n+1))*(2^(n+1)*(n+2)-(n+1))-2^(n+1)*(n+2)+(n-1);
vector(10, n, a(n-1)) \\ Altug Alkan, Oct 01 2015

a(n) = 2^(2^(n+1)*(n+2)-(n+1))*(2^(n+1)*(n+2)-(n+1))-2^(n+1)*(n+2)+(n-1).

A260003 Values f(1,x,y) with x>=0, y>0, in increasing order, where f is the Sudan function defined in A260002.

Original entry on oeis.org

1, 3, 4, 5, 7, 8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 21, 24, 25, 26, 27, 28, 29, 31, 32, 33, 35, 36, 37, 39, 40, 41, 42, 43, 44, 45, 47, 48, 49, 51, 52, 53, 55, 56, 57, 58, 59, 60, 61, 63, 64, 65, 66, 67, 69, 71, 72, 73, 74, 75

Offset: 1

Natan Arie Consigli, Jul 23 2015

nonn

Equivalently, numbers of the form 2^y(x+2)-y-2.
Using f(1,x,y) = f(0, f(1,x,y-1), f(1,x,y-1)+y) = 2*f(1,x,y-1) + y
f(1,x,y) + y + 2 = 2*(f(1,x,y-1)+y-1+2) let g(y) = f(1,x,y) + y + 2 then g(y) = 2*g(y-1). This means g(y)=2^y*g(0) and f(1,x,y) + y + 2 = 2^y(f(1,x,0)+2) but f(1,x,0) = x so f(1,x,y) = 2^y(x+2) - y - 2.
In this list we suppose that y>0. If we include y=0, every natural number would be in the sequence.

			19 is listed because f(1,1,3) = 2^3*(1+2) - 3 - 2 = 19.

Cf. A000325 (f(1,2,n)), A005408 (f(1,n,1)=2n+1), A048493 (f(1,n,2)), A079583 (f(1,1,n)), A123720 (f(1,4,n)), A133124(f(1,3,n)), A260002, A260004, A260005 (f(2,n,2)), A260006.

A260004 Values of f(2,x,y) in increasing order, for x>=0, y>0 where f is the Sudan function defined in A260002.

Original entry on oeis.org

1, 8, 19, 27, 74, 185, 440, 1015, 2294, 5109, 10228, 11252, 24563, 53234, 114673, 245744, 524271, 1114094, 2359277, 4980716, 10485739, 22020074, 46137321, 88080360, 96468968, 201326567, 419430374, 872415205, 1811939300, 15569256417

Offset: 1

Natan Arie Consigli, Jul 23 2015

nonn

This is a subsequence of A260003 since f(2,x,y)= f(1, f(2,x,y-1), f(2,x,y-1)+y).
In this list we suppose that y>0. If we take y=0, all the natural numbers would be in the sequence.
To evaluate the Sudan function see A260002-A260003.

			f(2,0,1) = f(1, f(2,0,0), f(2,0,0)+1) = f(1,0,1) = 2^1(0+2)-1-2 = 1;
f(2,0,2) = f(1, [f(2,0,1)], [f(2,0,1)+1+1]) = f(1,1,3) = 2^3(1+2)-3-2 = 19;

Cf. A048493 (f(2,n,1)), A260002, A260003, A260005 (f(2,n,2)), A260006.

A348257 Number of ways we can write [n] as the union of 2 sets of sizes i, j which intersect in exactly 2 elements (2 < i,j < n; i = j allowed).

Original entry on oeis.org

6, 30, 105, 315, 868, 2268, 5715, 14025, 33726, 79794, 186277, 429975, 982920, 2228088, 5013351, 11206485, 24903490, 55050030, 121110297, 265289475, 578813676, 1258290900, 2726297275, 5888802465, 12683574918, 27246198378, 58384711245, 124822486575, 266287971856, 566935682544

Offset: 4

Enrique Navarrete, Oct 08 2021

The terms in the sequence alternate 2 even and 2 odd.

			a(4) = 6 since we can write [4] as the following unions: {1,2,3} U {1,2,4}, {1,2,3} U {1,3,4}, {1,2,3} U {2,3,4}, {1,2,4} U {1,3,4}, {1,2,4} U {2,3,4}, {1,3,4} U {2,3,4}.

Index entries for linear recurrences with constant coefficients, signature (9,-33,63,-66,36,-8).

Cf. A000554, A260006.

nterms=50;Table[Binomial[n,2]*StirlingS2[n-2,2],{n,4,nterms+3}] (* Paolo Xausa, Nov 20 2021 *)

a(n) = (Sum_{j=3..n/2} binomial(n,j)*binomial(j,2)) + (1/2)*binomial(n,n/2+1) * binomial(n/2+1,2), if n is even.
a(n) = Sum_{j=3..ceiling(n/2)} binomial(n,j)*binomial(j,2), if n is odd.
G.f.: x^4*(6 - 24*x + 33*x^2 - 18*x^3 + 4*x^4)/((1 - x)^3*(1 - 2*x)^3). - Stefano Spezia, Oct 09 2021
a(n) = A000554(n)/2. - Enrique Navarrete, Nov 16 2021
a(n) = binomial(n,2) * Stirling2(n-2,2). - Alois P. Heinz, Nov 16 2021

A349415 Number of ways an n-set can be written as the union of 2 sets each with 4 or more elements and whose intersection contains exactly 3 elements.

Original entry on oeis.org

10, 60, 245, 840, 2604, 7560, 20955, 56100, 146146, 372372, 931385, 2293200, 5569880, 13368528, 31751223, 74709900, 174324430, 403700220, 928512277, 2122315800, 4823447300, 10905187800, 24536675475, 54962156340, 122607890874, 272461983780, 603308682865, 1331439856800

Offset: 5

Enrique Navarrete, Nov 16 2021

Starting at n=7, the terms in the sequence alternate one odd and 3 even.

			a(5)=10 since [5] can be written as the union of the following sets: {1,2,3,4} U {1,2,3,5}, {1,2,3,4} U {1,2,4,5}, {1,2,3,4} U {1,3,4,5}, {1,2,3,4} U {2,3,4,5}, {1,2,3,5} U {1,2,4,5}, {1,2,3,5} U {1,3,4,5},{1,2,3,5} U {2,3,4,5}, {1,2,4,5} U {1,3,4,5}, {1,2,4,5} U {2,3,4,5}, {1,3,4,5} U {2,3,4,5}.

Index entries for linear recurrences with constant coefficients, signature (12,-62,180,-321,360,-248,96,-16).

Cf. A052769, A260006, A348257.

a:= n-> binomial(n,3)*Stirling2(n-3,2):
seq(a(n), n=5..32);  # Alois P. Heinz, Nov 16 2021

nterms=50;Table[Binomial[n,3]*StirlingS2[n-3,2],{n,5,nterms+4}] (* Paolo Xausa, Nov 20 2021 *)

a(n) = Sum_{j=4..n/2+1} binomial(n,j)*binomial(j,3), n even.
a(n) = (Sum_{j=4..ceiling(n/2)} binomial(n,j)*binomial(j,3)) + (1/2)*binomial(n,ceiling(n/2)+1)*binomial(ceiling(n/2)+1,3), n odd.
From Alois P. Heinz, Nov 16 2021: (Start)
a(n) = binomial(n,3) * Stirling2(n-3,2).
G.f.: x^5*(8*x^6 - 48*x^5 + 124*x^4 - 180*x^3 + 145*x^2 - 60*x + 10)/((2*x-1)^4*(x-1)^4). (End)
E.g.f.: (1/12)*x^3*(exp(x)-1)^2.
a(n) = 12*a(n-1) - 62*a(n-2) + 180*a(n-3) - 321*a(n-4) + 360*a(n-5) - 248*a(n-6) + 96*a(n-7) - 16*a(n-8). - Wesley Ivan Hurt, Dec 03 2021

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A052749 a(n) = 2*n * Stirling2(n-1,2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

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

A260005 a(n) = f(2,n,2), where f is the Sudan function defined in A260002.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A260003 Values f(1,x,y) with x>=0, y>0, in increasing order, where f is the Sudan function defined in A260002.

Views

Author

Keywords

Comments

Examples

Crossrefs

A260004 Values of f(2,x,y) in increasing order, for x>=0, y>0 where f is the Sudan function defined in A260002.

Views

Author

Keywords

Comments

Examples

Crossrefs

A348257 Number of ways we can write [n] as the union of 2 sets of sizes i, j which intersect in exactly 2 elements (2 < i,j < n; i = j allowed).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A349415 Number of ways an n-set can be written as the union of 2 sets each with 4 or more elements and whose intersection contains exactly 3 elements.

Views

Author

Keywords

Comments

Examples

A052749 a(n) = 2n Stirling2(n-1,2).