OFFSET
0,2
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
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).
Andrei Asinowski, Cyril Banderier, 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, Kamal Ali Alezabi, Pseudorandom sequence contention algorithm for IEEE 802.11ah based internet of things network, PLoS ONE (2020) Vol. 15, No. 8, e0237386.
Index entries for linear recurrences with constant coefficients, signature (1,2,-2).
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
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(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
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
$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
(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
(Magma) [((5-(-1)^n)/2)*2^((2*n-1+(-1)^n)/4)-1: n in [0..45]]; // G. C. Greubel, Oct 22 2019
(Sage) [((5-(-1)^n)/2)*2^((2*n-1+(-1)^n)/4)-1 for n in (0..45)] # G. C. Greubel, Oct 22 2019
(GAP) List([0..45], n-> ((5-(-1)^n)/2)*2^((2*n-1+(-1)^n)/4)-1); # G. C. Greubel, Oct 22 2019
(Python)
def A052955(n): return ((2|n&1)<<(n>>1))-1 # Chai Wah Wu, Jul 13 2023
CROSSREFS
Essentially 1 more than A027383, 2 more than A060482. [Comment corrected by Klaus Brockhaus, Aug 09 2009]
For partial sums see A027383.
See A016116 for the first differences.
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
KEYWORD
easy,nonn,changed
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
Minor edits from N. J. A. Sloane, Jul 09 2022
STATUS
approved