login
The OEIS is supported by the many generous donors 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. 61

%I #168 Jul 13 2023 15:51:28

%S 1,2,3,5,7,11,15,23,31,47,63,95,127,191,255,383,511,767,1023,1535,

%T 2047,3071,4095,6143,8191,12287,16383,24575,32767,49151,65535,98303,

%U 131071,196607,262143,393215,524287,786431,1048575,1572863,2097151,3145727

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

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

%C 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

%C 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).

%C Number of binary palindromes < 2^n (see A006995). - _Hieronymus Fischer_, Feb 03 2012

%C Partial sums of A016116 (omitting the initial term). - _Hieronymus Fischer_, Feb 18 2012

%C 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

%C 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

%H Reinhard Zumkeller, <a href="/A052955/b052955.txt">Table of n, a(n) for n = 0..1000</a>

%H Andrei Asinowski, Cyril Banderier, Benjamin Hackl, <a href="https://benjamin-hackl.at/downloads/2019_ABH_popstack-extremal.pdf">On extremal cases of pop-stack sorting</a>, Permutation Patterns (Zürich, Switzerland, 2019).

%H Andrei Asinowski, Cyril Banderier, Benjamin Hackl, <a href="https://arxiv.org/abs/2003.04912">Flip-sort and combinatorial aspects of pop-stack sorting</a>, arXiv:2003.04912 [math.CO], 2020.

%H J.-L. Baril, T. Mansour, and A. Petrossian, <a href="http://jl.baril.u-bourgogne.fr/equival.pdf">Equivalence classes of permutations modulo excedances</a>, preprint, 2014.

%H J.-L. Baril, T. Mansour, and A. Petrossian, <a href="http://dx.doi.org/10.4310/JOC.2014.v5.n4.a4">Equivalence classes of permutations modulo excedances</a>, Journal of Combinatorics 5 (2014), 453-469.

%H David Blackman and Sebastiano Vigna, <a href="https://dl.acm.org/doi/10.1145/3460772">Scrambled Linear Pseudorandom Number Generators</a>, ACM Transactions on Mathematical Software, Vol. 47, No. 4, p. 1-32, 2021; <a href="https://arxiv.org/abs/1805.01407">arXiv preprint</a>, arXiv:1805.01407 [cs.DS], 2018.

%H James East, Jitender Kumar, James D. Mitchell, and Wilf A. Wilson, <a href="https://arxiv.org/abs/1706.04967">Maximal subsemigroups of finite transformation and partition monoids</a>, arXiv:1706.04967 [math.GR], 2017. [_Wilf A. Wilson_, Jul 21 2017]

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=1026">Encyclopedia of Combinatorial Structures 1026</a>

%H Mohammed A. Raouf, Fazirulhisyam Hashim, Jiun Terng Liew, Kamal Ali Alezabi, <a href="https://doi.org/10.1371/journal.pone.0237386">Pseudorandom sequence contention algorithm for IEEE 802.11ah based internet of things network</a>, PLoS ONE (2020) Vol. 15, No. 8, e0237386.

%H <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (1,2,-2).

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

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

%F 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.)

%F a(n) = 2^(n/2) * (3*sqrt(2)/4 + 1 - (3*sqrt(2)/4 - 1) * (-1)^n) - 1. - _Paul Barry_, May 23 2004

%F a(n) = 1 + Sum_{k=0..n-1} A016116(k). - _Robert G. Wilson v_, Jun 05 2004

%F A132340(a(n)) = A027383(n). - _Reinhard Zumkeller_, Aug 20 2007

%F a(n) = A027383(n-1) + 1 for n>0. - _Hieronymus Fischer_, Sep 15 2007

%F a(n) = A132666(a(n+1)-1). - _Hieronymus Fischer_, Sep 15 2007

%F a(n) = A132666(a(n-1)) + 1 for n>0. - _Hieronymus Fischer_, Sep 15 2007

%F A132666(a(n)) = a(n+1) - 1. - _Hieronymus Fischer_, Sep 15 2007

%F a(n) = A027383(n+1)/2. - _Zerinvary Lajos_, Mar 16 2008

%F a(n) = (5 - (-1)^n)/2*2^floor(n/2) - 1. - _Hieronymus Fischer_, Feb 03 2012

%F 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

%F a(n) = ((5 - (-1)^n)/2)*2^((2*n - 1 + (-1)^n)/4) - 1. - _Luce ETIENNE_, Sep 20 2014

%F a(n) = -(2^(n+1)) * A107659(-3-n) for all n in Z. - _Michael Somos_, Jun 24 2018

%F 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

%e 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

%p spec := [S,{S=Prod(Sequence(Prod(Union(Z,Z),Z)),Union(Sequence(Z),Z))}, unlabeled ]: seq(combstruct[count ](spec,size=n), n=0..20);

%p 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

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

%t a[0]=1; a[1]=2; a[n_]:= a[n]= 2 a[n-2] +1; Array[a, 42, 0]

%t a[n_]:= (2 + Mod[n, 2]) 2^Quotient[n, 2] - 1; (* _Michael Somos_, Jun 24 2018 *)

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

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

%o $lim = shift;

%o sub show{};

%o $n = $incr = $P = 1;

%o show($n, $incr, $P);

%o $incr = 1;

%o for $n (2..$lim) {

%o $P += $incr;

%o show($n, $P, $incr, $P);

%o $incr *=2 if ($n % 2); # double the increment after an odd n

%o }

%o sub show {

%o my($n, $P) = @_;

%o printf("%4d\t%16g\n", $n, $P);

%o }

%o # Mark A. Mandel (thnidu aT g ma(il) doT c0m), Dec 29 2010

%o (PARI) a(n)=(2+n%2)<<(n\2)-1 \\ _Charles R Greathouse IV_, Jun 19 2011

%o (PARI) {a(n) = (n%2 + 2) * 2^(n\2) - 1}; /* _Michael Somos_, Jun 24 2018 */

%o (Haskell)

%o a052955 n = a052955_list !! n

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

%o -- _Reinhard Zumkeller_, Feb 22 2012

%o (Magma) [((5-(-1)^n)/2)*2^((2*n-1+(-1)^n)/4)-1: n in [0..45]]; // _G. C. Greubel_, Oct 22 2019

%o (Sage) [((5-(-1)^n)/2)*2^((2*n-1+(-1)^n)/4)-1 for n in (0..45)] # _G. C. Greubel_, Oct 22 2019

%o (GAP) List([0..45], n-> ((5-(-1)^n)/2)*2^((2*n-1+(-1)^n)/4)-1); # _G. C. Greubel_, Oct 22 2019

%o (Python)

%o def A052955(n): return ((2|n&1)<<(n>>1))-1 # _Chai Wah Wu_, Jul 13 2023

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

%Y Essentially 1 more than A027383, 2 more than A060482. [Comment corrected by _Klaus Brockhaus_, Aug 09 2009]

%Y Union of A000225 & A055010.

%Y For partial sums see A027383.

%Y See A016116 for the first differences.

%Y Cf. A083329, A107659, A132666.

%Y 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

%K easy,nonn

%O 0,2

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

%E Formula and more terms from _Henry Bottomley_, May 03 2000

%E Additional comments from _Robert G. Wilson v_, Jan 29 2001

%E Minor edits from _N. J. A. Sloane_, Jul 09 2022

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 10:55 EDT 2024. Contains 371241 sequences. (Running on oeis4.)