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

1, 2, 3, 5, 7, 11, 15, 23, 31, 47, 63, 95, 127, 191, 255, 383, 511, 767, 1023, 1535, 2047, 3071, 4095, 6143, 8191, 12287, 16383, 24575, 32767, 49151, 65535, 98303, 131071, 196607, 262143, 393215, 524287, 786431, 1048575, 1572863, 2097151, 3145727

Offset: 0

Author

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

Keywords

• easy
• nonn

Comments

a(n) is the least k such that A056792(k) = n.

One quarter of the number of positive integer (n+2) X (n+2) arrays with every 2 X 2 subblock summing to 1. - R. H. Hardin, Sep 29 2008

Number of length n+1 left factors of Dyck paths having no DUU's (here U=(1,1) and D=(1,-1)). Example: a(4)=7 because we have UDUDU, UUDDU, UUDUD, UUUDD, UUUDU, UUUUD, and UUUUU (the paths UDUUD, UDUUU, and UUDUU do not qualify).

Number of binary palindromes < 2^n (see A006995). - Hieronymus Fischer, Feb 03 2012

Partial sums of A016116 (omitting the initial term). - Hieronymus Fischer, Feb 18 2012

a(n - 1), n > 1, is the number of maximal subsemigroups of the monoid of order-preserving or -reversing partial injective mappings on a set with n elements. - Wilf A. Wilson, Jul 21 2017

Number of monomials of the algebraic normal form of the Boolean function representing the n-th bit of the product 3x in terms of the bits of x. - Sebastiano Vigna, Oct 04 2020

Examples

			G.f. = 1 + 2*x + 3*x^2 + 5*x^3 + 7*x^4 + 11*x^5 + 15*x^6 + 23*x^7 + ... - _Michael Somos_, Jun 24 2018
		

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
• Andrei Asinowski, Cyril Banderier, and Benjamin Hackl, On extremal cases of pop-stack sorting, Permutation Patterns (Zürich, Switzerland, 2019).
• Andrei Asinowski, Cyril Banderier, and Benjamin Hackl, Flip-sort and combinatorial aspects of pop-stack sorting, arXiv:2003.04912 [math.CO], 2020.
• J.-L. Baril, T. Mansour, and A. Petrossian, Equivalence classes of permutations modulo excedances, preprint, 2014.
• J.-L. Baril, T. Mansour, and A. Petrossian, Equivalence classes of permutations modulo excedances, Journal of Combinatorics 5 (2014), 453-469.
• David Blackman and Sebastiano Vigna, Scrambled Linear Pseudorandom Number Generators, ACM Transactions on Mathematical Software, Vol. 47, No. 4, p. 1-32, 2021; arXiv preprint, arXiv:1805.01407 [cs.DS], 2018.
• James East, Jitender Kumar, James D. Mitchell, and Wilf A. Wilson, Maximal subsemigroups of finite transformation and partition monoids, arXiv:1706.04967 [math.GR], 2017. [_Wilf A. Wilson_, Jul 21 2017]
• Brian Hopkins and Aram Tangboonduangjit, Water Cells in Compositions of 1s and 2s, arXiv:2412.11528 [math.CO], 2024. See p. 9.
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1026
• Mohammed A. Raouf, Fazirulhisyam Hashim, Jiun Terng Liew, and Kamal Ali Alezabi, Pseudorandom sequence contention algorithm for IEEE 802.11ah based internet of things network, PLoS ONE (2020) Vol. 15, No. 8, e0237386.
• Mark Shattuck, Further Results for the Capacity Statistic Distribution on Compositions of 1's and 2's, arXiv:2501.09931 [math.CO], 2025. See p. 3.
• Index to sequences related to the complexity of n
• Index entries for linear recurrences with constant coefficients, signature (1,2,-2).

Crossrefs

Cf. A000225 for even terms, A055010 for odd terms. See also A056792.

Essentially 1 more than A027383, 2 more than A060482. [Comment corrected by Klaus Brockhaus, Aug 09 2009]

Union of A000225 & A055010.

For partial sums see A027383.

See A016116 for the first differences.

Cf. A083329, A107659, A132666.

The following sequences are all essentially the same, in the sense that they are simple transformations of each other, with A029744 = {s(n), n>=1}, the numbers 2^k and 3*2^k, as the parent: A029744 (s(n)); A052955 (s(n)-1), A027383 (s(n)-2), A354788 (s(n)-3), A347789 (s(n)-4), A209721 (s(n)+1), A209722 (s(n)+2), A343177 (s(n)+3), A209723 (s(n)+4); A060482, A136252 (minor differences from A354788 at the start); A354785 (3*s(n)), A354789 (3*s(n)-7). The first differences of A029744 are 1,1,1,2,2,4,4,8,8,... which essentially matches eight sequences: A016116, A060546, A117575, A131572, A152166, A158780, A163403, A320770. The bisections of A029744 are A000079 and A007283. - N. J. A. Sloane, Jul 14 2022

Programs

GAP

List([0..45], n-> ((5-(-1)^n)/2)*2^((2*n-1+(-1)^n)/4)-1); # G. C. Greubel, Oct 22 2019

Haskell

a052955 n = a052955_list !! n
a052955_list = 1 : 2 : map ((+ 1) . (* 2)) a052955_list
-- Reinhard Zumkeller, Feb 22 2012

Magma

[((5-(-1)^n)/2)*2^((2*n-1+(-1)^n)/4)-1: n in [0..45]]; // G. C. Greubel, Oct 22 2019

Maple

spec := [S,{S=Prod(Sequence(Prod(Union(Z,Z),Z)),Union(Sequence(Z),Z))}, unlabeled ]: seq(combstruct[count ](spec,size=n), n=0..20);
a[0]:=0:a[1]:=1:for n from 2 to 100 do a[n]:=2*a[n-2]+2 od: seq(a[n]/2, n=2..43); # Zerinvary Lajos, Mar 16 2008

Mathematica

a[n_]:= If[EvenQ[n], 2^(n/2+1) -1, 3*2^((n-1)/2) -1]; Table[a[n], {n, 0, 41}] (* Robert G. Wilson v, Jun 05 2004 *)
a[0]=1; a[1]=2; a[n_]:= a[n]= 2 a[n-2] +1; Array[a, 42, 0]
a[n_]:= (2 + Mod[n, 2]) 2^Quotient[n, 2] - 1; (* Michael Somos, Jun 24 2018 *)

PARI

a(n)=(2+n%2)<<(n\2)-1 \\ Charles R Greathouse IV, Jun 19 2011

PARI

{a(n) = (n%2 + 2) * 2^(n\2) - 1}; /* Michael Somos, Jun 24 2018 */

Perl

# command line argument tells how high to take n
# Beyond a(38) = 786431 you may need a special code to handle large integers
  $lim = shift;
  sub show{};
$n = $incr = $P = 1;
show($n, $incr, $P);
$incr = 1;
for $n (2..$lim) {
    $P += $incr;
    show($n, $P, $incr, $P);
    $incr *=2 if ($n % 2); # double the increment after an odd n
}
sub show {
    my($n, $P) = @_;
    printf("%4d\t%16g\n", $n, $P);
}
# Mark A. Mandel (thnidu aT  g ma(il) doT c0m), Dec 29 2010

Python

def A052955(n): return ((2|n&1)<<(n>>1))-1 # Chai Wah Wu, Jul 13 2023

Sage

[((5-(-1)^n)/2)*2^((2*n-1+(-1)^n)/4)-1 for n in (0..45)] # G. C. Greubel, Oct 22 2019

Formula

a(0)=1, a(1)=2; thereafter a(n) = 2*a(n-2) + 1, n >= 2.

G.f.: (1 + x - x^2)/((1 - x)*(1 - 2*x^2)).

a(n) = -1 + Sum_{alpha = RootOf(-1 + 2*Z^2)} (1/4) * (3 + 4*alpha) * alpha^(-1-n). (That is, the sum is indexed by the roots of the polynomial -1 + 2*Z^2.)

a(n) = 2^(n/2) * (3*sqrt(2)/4 + 1 - (3*sqrt(2)/4 - 1) * (-1)^n) - 1. - Paul Barry, May 23 2004

a(n) = 1 + Sum_{k=0..n-1} A016116(k). - Robert G. Wilson v, Jun 05 2004

A132340(a(n)) = A027383(n). - Reinhard Zumkeller, Aug 20 2007

From Hieronymus Fischer, Sep 15 2007: (Start)

a(n) = A027383(n-1) + 1 for n>0.

a(n) = A132666(a(n+1)-1).

a(n) = A132666(a(n-1)) + 1 for n>0.

A132666(a(n)) = a(n+1) - 1. (End)

a(n) = A027383(n+1)/2. - Zerinvary Lajos, Mar 16 2008

a(n) = (5 - (-1)^n)/2*2^floor(n/2) - 1. - Hieronymus Fischer, Feb 03 2012

a(2n+1) = (a(2*n) + a(2*n+2))/2. Combined with a(n) = 2*a(n-2) + 1, n >= 2 and a(0) = 1, this specifies the sequence. - Richard R. Forberg, Nov 30 2013

a(n) = ((5 - (-1)^n)/2)*2^((2*n - 1 + (-1)^n)/4) - 1. - Luce ETIENNE, Sep 20 2014

a(n) = -(2^(n+1)) * A107659(-3-n) for all n in Z. - Michael Somos, Jun 24 2018

E.g.f.: (1/4)*exp(-sqrt(2)*x)*(4 - 3*sqrt(2) + (4 + 3*sqrt(2))*exp(2*sqrt(2)*x) - 4*exp(x + sqrt(2)*x)). - Stefano Spezia, Oct 22 2019

A term k appears in this sequence <=> 4 does not divide binomial(k, j) for any j in 0..k. - Peter Luschny, Jun 28 2025

Extensions

Formula and more terms from Henry Bottomley, May 03 2000

Additional comments from Robert G. Wilson v, Jan 29 2001

Minor edits from N. J. A. Sloane, Jul 09 2022