A304371 -id:A304371 - cp's OEIS frontend

A036563 a(n) = 2^n - 3.

-2, -1, 1, 5, 13, 29, 61, 125, 253, 509, 1021, 2045, 4093, 8189, 16381, 32765, 65533, 131069, 262141, 524285, 1048573, 2097149, 4194301, 8388605, 16777213, 33554429, 67108861, 134217725, 268435453, 536870909, 1073741821, 2147483645

Offset: 0

N. J. A. Sloane

a(n+1) is the n-th number with exactly n 1's in binary representation. - Reinhard Zumkeller, Mar 06 2003
Berstein and Onn: "For every m = 3k+1, the Graver complexity of the vertex-edge incidence matrix of the complete bipirtite graph K(3,m) satisfies g(m) >= 2^(k+2)-3." - Jonathan Vos Post, Sep 15 2007
Row sums of triangle A135857. - Gary W. Adamson, Dec 01 2007
a(n) = A164874(n-1,n-2) for n > 2. - Reinhard Zumkeller, Aug 29 2009
Starting (1, 5, 13, ...) = eigensequence of a triangle with A016777: (1, 4, 7, 10, ...) as the left border and the rest 1's. - Gary W. Adamson, Jul 24 2010
An elephant sequence, see A175655. For the central square just one A[5] vector, with decimal value 186, leads to this sequence (n >= 2). For the corner squares this vector leads to the companion sequence A123203. - Johannes W. Meijer, Aug 15 2010
First differences of A095264: A095264(n+1) - A095264(n) = a(n+2). - J. M. Bergot, May 13 2013
a(n+2) is given by the sum of n-th row of triangle of powers of 2: 1; 2 1 2; 4 2 1 2 4; 8 4 2 1 2 4 8; ... - Philippe Deléham, Feb 24 2014
Also, the decimal representation of the x-axis, from the left edge to the origin, of the n-th stage of growth of the two-dimensional cellular automaton defined by "Rule 643", based on the 5-celled von Neumann neighborhood, initialized with a single black (ON) cell at stage zero. See A283508. - Robert Price, Mar 09 2017
a(n+3) is the value of the Ackermann function A(3,n) or ack(3,n). - Olivier Gérard, May 11 2018

			a(2) = 1;
a(3) = 2 + 1 + 2 = 5;
a(4) = 4 + 2 + 1 + 2 + 4 = 13;
a(5) = 8 + 4 + 2 + 1 + 2 + 4 + 8 = 29; etc. - _Philippe Deléham_, Feb 24 2014

Vincenzo Librandi, Table of n, a(n) for n = 0..500
Paul Barry, Conjectures and results on some generalized Rueppel sequences, arXiv:2107.00442 [math.CO], 2021.
Yael Berstein and Shmuel Onn, The Graver complexity of integer programming, Annals of Combinatorics, Vol. 13, No. 3 (2009), pp. 289-296; arXiv preprint, arXiv:0709.1500 [math.CO], 2007.
L' Education Mathématique, Problème 8907, 49e Annee, No 14, 15 Avril 1947, p. 113
Irving Kaplansky and John Riordan, The problem of the rooks and its applications, in Combinatorics, Duke Mathematical Journal, 13.2 (1946): 259-268. [Annotated scanned copy]
Irving Kaplansky and John Riordan, The problem of the rooks and its applications, Duke Mathematical Journal 13.2 (1946): 259-268. Sequence is on page 267.
Index entries for linear recurrences with constant coefficients, signature (3,-2).

Row sums of triangular array A027960. A column of A119725.
Cf. A081118, A130459, A131112, A050414, A050415, A135857, A000079, A016777, A283508.
Cf. A074877, A304370, A304371, A331372.

List([0..40], n-> 2^n -3); # G. C. Greubel, Nov 18 2019

[2^n-3: n in [0..40]]; // Vincenzo Librandi, May 09 2011

A036563:=n->2^n-3; seq(A036563(n), n=0..40); # Wesley Ivan Hurt, Jun 26 2014

Table[2^n - 3, {n, 0, 40}] (* Wesley Ivan Hurt, Jun 26 2014 *)
LinearRecurrence[{3,-2},{-2,-1},40] (* Harvey P. Dale, Sep 26 2018 *)

a(n)= 2^n-3 \\ Charles R Greathouse IV, Dec 22 2011

def A036563(n): return (1<Chai Wah Wu, Sep 27 2024

[gaussian_binomial(n,1,2)-2 for n in range(0,40)] # Zerinvary Lajos, May 31 2009

a(n) = 2*a(n-1) + 3.
The sequence 1, 5, 13, ... has a(n) = 4*2^n-3. These are the partial sums of A151821. - Paul Barry, Aug 25 2003
a(n) = A118654(n-3, 6), for n > 2. - N. J. A. Sloane, Sep 29 2006
Row sums of triangle A130459 starting (1, 5, 13, 29, 61, ...). - Gary W. Adamson, May 26 2007
Row sums of triangle A131112. - Gary W. Adamson, Jun 15 2007
Binomial transform of [1, 4, 4, 4, ...] = (1, 5, 13, 29, 61, ...). - Gary W. Adamson, Sep 20 2007
a(n) = 2*StirlingS2(n,2) - 1, for n > 0. - Ross La Haye, Jul 05 2008
a(n) = A000079(n) - 3. - Omar E. Pol, Dec 21 2008
From Mohammad K. Azarian, Jan 14 2009: (Start)
G.f.: 1/(1-2*x) - 3/(1-x).
E.g.f.: exp(2*x) - 3*exp(x). (End)
For n >= 3, a(n) = 2<+>n, where operation <+> is defined in A206853. - Vladimir Shevelev, Feb 17 2012
a(n) = 3*a(n-1) - 2*a(n-2) for n > 1, a(0)=-2, a(1)=-1. - Philippe Deléham, Dec 23 2013
Sum_{n>=1} 1/a(n) = A331372. - Amiram Eldar, Nov 18 2020

A074877 Number of function calls required to compute ack(3,n), where ack denotes the Ackermann function.

Original entry on oeis.org

15, 106, 541, 2432, 10307, 42438, 172233, 693964, 2785999, 11164370, 44698325, 178875096, 715664091, 2862983902, 11452590817, 45811673828, 183249316583, 733002509034, 2932020521709, 11728103058160, 46912454175475, 187649900587766, 750599770123001, 3002399416036092

Offset: 0

Jeff Medha (medha_jeff(AT)yahoo.co.in), Sep 12 2002

The Ackermann function is defined recursively for nonnegative integers m,n by: ack(0,n) = n + 1 if m=0; ack(m,0) = ack(m-1,1) if m>0 and n=0; ack(m,n) = ack(m-1,ack(m,n-1)) otherwise.

Gert Bultman, Ackermann function.
Y. Sundblad, The Ackermann function. A theoretical, computational and formula manipulative study, Nordisk Tidskr. Informationsbehandling (BIT) 11 (1971), 107-119.
Eric Weisstein's World of Mathematics, Ackermann function.
Wikipedia, Ackermann function.
Index entries for sequences related to Ackermann function
Index entries for linear recurrences with constant coefficients, signature (8,-21,22,-8).

Two kinds of calls: A304370, A304371.

[128/3*4^n-40*2^n+3*n+37/3: n in [0..30]]; // Vincenzo Librandi, Apr 19 2015

Table[128 / 3 4^n - 40 2^n + 3 n + 37 / 3, {n, 0, 30}] (* Vincenzo Librandi, Apr 19 2015 *)

a(n)=128/3*4^n-40*2^n+3*n+37/3 \\ Charles R Greathouse IV, Dec 09 2011

G.f.: (15-14*x+8*x^2)/((4*x-1)*(2*x-1)*(x-1)^2); recurrence: a(n) = 8*a(n-1)-21*a(n-2)+22*a(n-3)-8*a(n-4); a(n) = 128/3*4^n-40*2^n+3*n+37/3 for n>=0. - Pab Ter (pabrlos(AT)yahoo.com), May 29 2004

a(n) ~ 128/3*4^n. [Charles R Greathouse IV, Dec 09 2011]

Edited by Pab Ter (pabrlos(AT)yahoo.com), May 29 2004

More terms from Vincenzo Librandi, Apr 19 2015

A304370 Number of function calls of the first kind required to compute ack(3,n), where ack denotes the Ackermann function.

Original entry on oeis.org

9, 58, 283, 1244, 5213, 21342, 86367, 347488, 1394017, 5584226, 22353251, 89445732, 357848421, 1431524710, 5726360935, 22905967976, 91624920425, 366501778794, 1466011309419, 5864053626220, 23456231282029, 93824958682478, 375299901838703, 1501199741572464

Offset: 0

Olivier Gérard, May 11 2018

The distinction between different kinds of recursive calls is based on a naive implementation of the Ackermann function in C.
int ack(int m, int n)
{
// Final result
....if (m==0) return n + 1;
.
// Recursive calls of the first kind:
....if (n==0) return ack(m - 1, 1);
.
// Recursive calls of the second kind:
....return ack(m - 1, ack(m, n - 1));
}

Index entries for linear recurrences with constant coefficients, signature (8,-21,22,-8).

Cf. A036563, A074877, A304371.

G.f.: (8*x^2-14*x+9)/((4*x-1)*(2*x-1)*(x-1)^2). - Alois P. Heinz, May 12 2018

cp's OEIS Frontend

A036563 a(n) = 2^n - 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Python

Sage

Formula

A074877 Number of function calls required to compute ack(3,n), where ack denotes the Ackermann function.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A304370 Number of function calls of the first kind required to compute ack(3,n), where ack denotes the Ackermann function.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula