cp's OEIS Frontend

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

%I A052955 #182 Jun 28 2025 11:10:26
%S A052955 1,2,3,5,7,11,15,23,31,47,63,95,127,191,255,383,511,767,1023,1535,
%T A052955 2047,3071,4095,6143,8191,12287,16383,24575,32767,49151,65535,98303,
%U A052955 131071,196607,262143,393215,524287,786431,1048575,1572863,2097151,3145727
%N A052955 a(2n) = 2*2^n - 1, a(2n+1) = 3*2^n - 1.
%C A052955 a(n) is the least k such that A056792(k) = n.
%C A052955 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 A052955 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 A052955 Number of binary palindromes < 2^n (see A006995). - _Hieronymus Fischer_, Feb 03 2012
%C A052955 Partial sums of A016116 (omitting the initial term). - _Hieronymus Fischer_, Feb 18 2012
%C A052955 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 A052955 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 A052955 Reinhard Zumkeller, <a href="/A052955/b052955.txt">Table of n, a(n) for n = 0..1000</a>
%H A052955 Andrei Asinowski, Cyril Banderier, and 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 A052955 Andrei Asinowski, Cyril Banderier, and 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 A052955 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 A052955 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 A052955 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 A052955 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 A052955 Brian Hopkins and Aram Tangboonduangjit, <a href="https://arxiv.org/abs/2412.11528">Water Cells in Compositions of 1s and 2s</a>, arXiv:2412.11528 [math.CO], 2024. See p. 9.
%H A052955 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=1026">Encyclopedia of Combinatorial Structures 1026</a>
%H A052955 Mohammed A. Raouf, Fazirulhisyam Hashim, Jiun Terng Liew, and 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 A052955 Mark Shattuck, <a href="https://arxiv.org/abs/2501.09931">Further Results for the Capacity Statistic Distribution on Compositions of 1's and 2's</a>, arXiv:2501.09931 [math.CO], 2025. See p. 3.
%H A052955 <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%H A052955 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (1,2,-2).
%F A052955 a(0)=1, a(1)=2; thereafter a(n) = 2*a(n-2) + 1, n >= 2.
%F A052955 G.f.: (1 + x - x^2)/((1 - x)*(1 - 2*x^2)).
%F A052955 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 A052955 a(n) = 2^(n/2) * (3*sqrt(2)/4 + 1 - (3*sqrt(2)/4 - 1) * (-1)^n) - 1. - _Paul Barry_, May 23 2004
%F A052955 a(n) = 1 + Sum_{k=0..n-1} A016116(k). - _Robert G. Wilson v_, Jun 05 2004
%F A052955 A132340(a(n)) = A027383(n). - _Reinhard Zumkeller_, Aug 20 2007
%F A052955 From _Hieronymus Fischer_, Sep 15 2007: (Start)
%F A052955 a(n) = A027383(n-1) + 1 for n>0.
%F A052955 a(n) = A132666(a(n+1)-1).
%F A052955 a(n) = A132666(a(n-1)) + 1 for n>0.
%F A052955 A132666(a(n)) = a(n+1) - 1. (End)
%F A052955 a(n) = A027383(n+1)/2. - _Zerinvary Lajos_, Mar 16 2008
%F A052955 a(n) = (5 - (-1)^n)/2*2^floor(n/2) - 1. - _Hieronymus Fischer_, Feb 03 2012
%F A052955 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 A052955 a(n) = ((5 - (-1)^n)/2)*2^((2*n - 1 + (-1)^n)/4) - 1. - _Luce ETIENNE_, Sep 20 2014
%F A052955 a(n) = -(2^(n+1)) * A107659(-3-n) for all n in Z. - _Michael Somos_, Jun 24 2018
%F A052955 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
%F A052955 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
%e A052955 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 A052955 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 A052955 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 A052955 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 A052955 a[0]=1; a[1]=2; a[n_]:= a[n]= 2 a[n-2] +1; Array[a, 42, 0]
%t A052955 a[n_]:= (2 + Mod[n, 2]) 2^Quotient[n, 2] - 1; (* _Michael Somos_, Jun 24 2018 *)
%o A052955 (Perl)# command line argument tells how high to take n
%o A052955 # Beyond a(38) = 786431 you may need a special code to handle large integers
%o A052955   $lim = shift;
%o A052955   sub show{};
%o A052955 $n = $incr = $P = 1;
%o A052955 show($n, $incr, $P);
%o A052955 $incr = 1;
%o A052955 for $n (2..$lim) {
%o A052955     $P += $incr;
%o A052955     show($n, $P, $incr, $P);
%o A052955     $incr *=2 if ($n % 2); # double the increment after an odd n
%o A052955 }
%o A052955 sub show {
%o A052955     my($n, $P) = @_;
%o A052955     printf("%4d\t%16g\n", $n, $P);
%o A052955 }
%o A052955 # Mark A. Mandel (thnidu aT  g ma(il) doT c0m), Dec 29 2010
%o A052955 (PARI) a(n)=(2+n%2)<<(n\2)-1 \\ _Charles R Greathouse IV_, Jun 19 2011
%o A052955 (PARI) {a(n) = (n%2 + 2) * 2^(n\2) - 1}; /* _Michael Somos_, Jun 24 2018 */
%o A052955 (Haskell)
%o A052955 a052955 n = a052955_list !! n
%o A052955 a052955_list = 1 : 2 : map ((+ 1) . (* 2)) a052955_list
%o A052955 -- _Reinhard Zumkeller_, Feb 22 2012
%o A052955 (Magma) [((5-(-1)^n)/2)*2^((2*n-1+(-1)^n)/4)-1: n in [0..45]]; // _G. C. Greubel_, Oct 22 2019
%o A052955 (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 A052955 (GAP) List([0..45], n-> ((5-(-1)^n)/2)*2^((2*n-1+(-1)^n)/4)-1); # _G. C. Greubel_, Oct 22 2019
%o A052955 (Python)
%o A052955 def A052955(n): return ((2|n&1)<<(n>>1))-1 # _Chai Wah Wu_, Jul 13 2023
%Y A052955 Cf. A000225 for even terms, A055010 for odd terms. See also A056792.
%Y A052955 Essentially 1 more than A027383, 2 more than A060482. [Comment corrected by _Klaus Brockhaus_, Aug 09 2009]
%Y A052955 Union of A000225 & A055010.
%Y A052955 For partial sums see A027383.
%Y A052955 See A016116 for the first differences.
%Y A052955 Cf. A083329, A107659, A132666.
%Y A052955 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 A052955 easy,nonn
%O A052955 0,2
%A A052955 encyclopedia(AT)pommard.inria.fr, Jan 25 2000
%E A052955 Formula and more terms from _Henry Bottomley_, May 03 2000
%E A052955 Additional comments from _Robert G. Wilson v_, Jan 29 2001
%E A052955 Minor edits from _N. J. A. Sloane_, Jul 09 2022