A260002 -id:A260002 - cp's OEIS frontend

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

0, 3, 12, 35, 90, 217, 504, 1143, 2550, 5621, 12276, 26611, 57330, 122865, 262128, 557039, 1179630, 2490349, 5242860, 11010027, 23068650, 48234473, 100663272, 209715175, 436207590, 905969637, 1879048164, 3892314083, 8053063650, 16642998241, 34359738336

Offset: 0

Natan Arie Consigli, Jul 23 2015

f(1,n,n) = 2^n*(n+2) - (n+2) = (2^n - 1)*(n+2).
To evaluate the Sudan function see A260002 and A260003.
The numbers are alternately even and odd because for even n (2^n-1)*(n+2) is even and (2^(n+1)-1)*(n+1+2) is odd.
From Enrique Navarrete, Oct 02 2021: (Start)
a(n-2) is the number of ways we can write [n] as the union of 2 sets of sizes i, j which intersect in exactly 1 element (1 < i, j < n;  i = j allowed), n>=2.
For n = 4, a(n-2) = 12 since [4] can be written as the unions:
{1,2} U {1,3,4}; {2,3} U {1,2,4}; {1,2} U {2,3,4}; {2,3} U {1,3,4};
{1,3} U {1,2,4}; {2,4} U {1,2,3}; {1,3} U {2,3,4}; {2,4} U {1,3,4};
{1,4} U {1,2,3}; {3,4} U {1,2,3}; {1,4} U {2,3,4}; {3,4} U {1,2,4}. (End)

			a(4) = (2^4 - 1)*(4 + 2) = 90.

Colin Barker, Table of n, a(n) for n = 0..1000
Wikipedia, Sudan function (see diagonal of "Values of F1(x, y)" table).
Index entries for linear recurrences with constant coefficients, signature (6,-13,12,-4).

Cf. A000295 (f(1,0,n)), A000325 (f(1,2,n)), A005408 (f(1,n,1) = 2n+1), A001787 (n*2^(n-1)), A079583 (f(1,1,n)), A123720 (f(1,4,n)), A133124 (f(1,3,n)).
Cf. A260002, A260003, A260004, A260005.
Cf. A000984, A002697, A303602.

[(2^n-1)*(n+2): n in [0..30]]; // Vincenzo Librandi, Aug 22 2015

Table[(2^n -1)(n+2), {n, 0, 30}] (* Michael De Vlieger, Aug 22 2015 *)
CoefficientList[Series[x(3 -6x +2x^2)/((1-x)^2 (1-2x)^2), {x, 0, 40}], x] (* Vincenzo Librandi, Aug 22 2015 *)
LinearRecurrence[{6,-13,12,-4},{0,3,12,35},40] (* Harvey P. Dale, Mar 04 2023 *)

vector(40, n, n--; (2^n-1)*(n+2)) \\ Michel Marcus, Jul 29 2015

concat(0, Vec(x*(3-6*x+2*x^2)/((1-x)^2*(1-2*x)^2) + O(x^40))) \\ Colin Barker, Jul 29 2015

[(n+2)*(2^n -1) for n in (0..30)] # G. C. Greubel, Dec 30 2021

a(n) = (2^n -1)*(n+2).
a(n) = 6*a(n-1) - 13*a(n-2) + 12*a(n-3) - 4*a(n-4) for n>3. - Colin Barker, Jul 29 2015
G.f.: x*(3 - 6*x + 2*x^2) / ((1-x)^2*(1-2*x)^2). - Colin Barker, Jul 29 2015
E.g.f.: 2*(x+1)*exp(2*x) - (x+2)*exp(x). - Robert Israel, Aug 23 2015
From Enrique Navarrete, Oct 02 2021: (Start)
a(n-2) = Sum_{j=2..n/2} binomial(n,j)*j, n even > 2.
a(n-2) = (Sum_{j=2..floor(n/2)} binomial(n,j)*j) + (1/2)*binomial(n, ceiling(n/2))*ceiling(n/2), n odd > 1. (End)
From Wolfdieter Lang, Nov 12 2021: (Start)
The previous bisection becomes for a(n):
a(2*k) = 2*(A002697(k+1) - (k+1)), and a(2*k+1) = A303602(k+1) - (2*k+3)*(2 - A000984(k+1))/2 = (2*k+3)*(4^(k+1) - 2)/2, for k >= 0. (End)

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.

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

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Sage

Formula

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

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions