login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A052955 a(2n) = 2*2^n - 1, a(2n+1) = 3*2^n - 1. 35
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

a(n) = 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

LINKS

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000

Andrei Asinowski, Cyril Banderier, Benjamin Hackl, On extremal cases of pop-stack sorting, Permutation Patterns (Z├╝rich, Switzerland, 2019).

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, 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]

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1026

Index to sequences related to the complexity of n

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

FORMULA

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

G.f.: (1 + x - x^2)/((1 - x)*(1 - 2*x^2)). a(n) = 2*a(n-2) + 1, n>=2.

a(n) = 1 + partial sum of A016116(k-1). - Robert G. Wilson v, Jun 05 2004

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

a(n) = A027383(n-1)+1 for n>0. - Hieronymus Fischer, Sep 15 2007

a(n) = A132666(a(n+1)-1). - Hieronymus Fischer, Sep 15 2007

a(n) = A132666(a(n-1))+1 for n>0. - Hieronymus Fischer, Sep 15 2007

A132666(a(n)) = a(n+1)-1. - Hieronymus Fischer, Sep 15 2007

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(2n) + a(2n+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(0) = 1; a(1) = 2; a(n) = 1 + 2 * a(n-2), n >= 2. - Daniel Forgues, Feb 24 2015

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

EXAMPLE

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

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 *)

PROG

(Perl)# command line argument tells how high to take n

# Beyond a(38) = 786431 you may need a special code to handle large integers

# Mark A. Mandel (thnidu aT  g ma(il) doT c0m) 2010-12-29

  $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);

}

(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 */

(Haskell)

a052955 n = a052955_list !! n

a052955_list = 1 : 2 : map ((+ 1) . (* 2)) a052955_list

-- Reinhard Zumkeller, Feb 22 2012

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.

Sequence in context: A024792 A280661 A055771 * A326466 A326591 A177485

Adjacent sequences:  A052952 A052953 A052954 * A052956 A052957 A052958

KEYWORD

easy,nonn

AUTHOR

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

EXTENSIONS

Formula and more terms from Henry Bottomley, May 03 2000

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 19 13:01 EDT 2019. Contains 328222 sequences. (Running on oeis4.)