A052944 - OEIS

%I #92 Sep 08 2022 08:44:59

%S 0,2,5,10,19,36,69,134,263,520,1033,2058,4107,8204,16397,32782,65551,

%T 131088,262161,524306,1048595,2097172,4194325,8388630,16777239,

%U 33554456,67108889,134217754,268435483,536870940,1073741853,2147483678

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

%C Shortest length of bit-string containing all bit-strings of given length n. - _Rainer Rosenthal_, Apr 30 2003

%C Such a bitstring can be obtained by taking a length-2^n binary de Bruijn sequence and repeating the n-1 initial symbols at the end. - _Joerg Arndt_, Mar 16 2015

%C Bit string definition is equivalent to minimum number of tosses of a coin to achieve all possible outcomes of n tosses. - _Maurizio De Leo_, Mar 01 2015

%C Also the indices of Fermat numbers that can be represented as cyclotomic numbers. Specifically, F(a(n)) = cyclotomic(2^2^n,2^2^n). - _T. D. Noe_, Oct 17 2003

%C a(n) = A006127(n) - 1. - _Reinhard Zumkeller_, Apr 13 2011

%C Randomly select (with uniform distribution) a length n binary word w. a(n) is apparently the expected wait time for the first occurrence of w over all infinite binary sequences. For example: a(4)=19. We consider A005434(4)=4 distinct classes of length 4 binary words that share the same autocorrelation. There are A003000(4)=6 words that have waiting time = 16; 2 words with waiting time =20; 6 words with waiting time = 18; and 2 words with waiting time =30. 1/16*(6*16 + 2*20 + 6*18 + 2*30) = 19. - _Geoffrey Critzer_, Feb 27 2014

%D Discussed in newsgroup de.rec.denksport in Apr 2003

%D N. G. de Bruijn: A combinatorial problem. Indagationes Math. 8 (1946), pp. 461-467.

%H Vincenzo Librandi, <a href="/A052944/b052944.txt">Table of n, a(n) for n = 0..1000</a>

%H Adam M. Goyt and Lara K. Pudwell, <a href="http://arxiv.org/abs/1203.3786">Avoiding colored partitions of two elements in the pattern sense</a>, arXiv preprint arXiv:1203.3786 [math.CO], 2012; <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Goyt/goyt4.html">J. Int. Seq. 15 (2012) # 12.6.2</a>.

%H A. M. Hinz, S. Klavžar, U. Milutinović, C. Petr, <a href="http://dx.doi.org/10.1007/978-3-0348-0237-6">The Tower of Hanoi - Myths and Maths</a>, Birkhäuser 2013. See page 178. <a href="http://tohbook.info">Book's website</a>

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

%H Viktor Lopatkin, Pasha Zusmanovich, <a href="https://arxiv.org/abs/1907.03690">Commutative Lie algebras and commutative cohomology in characteristic 2</a>, arXiv:1907.03690 [math.KT], 2019.

%H T. Manneville, V. Pilaud, <a href="http://arxiv.org/abs/1501.07152">Compatibility fans for graphical nested complexes</a>, arXiv preprint arXiv:1501.07152 [math.CO], 2015-2016.

%H E. H. Rivals, <a href="http://www.lirmm.fr/~rivals/RESEARCH/PERIOD/"> Autocorrelation of Strings</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CyclotomicPolynomial.html">Cyclotomic Polynomial</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CoinTossing.html">Coin Tossing</a>

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

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

%F a(n+1) = 2*a(n) - n + 2 with a(0)=0. - Pieter Moree, Mar 06 2004

%F For n>=1: partial sums of A000051. - _Emeric Deutsch_, Mar 04 2004

%F a(0)=0, a(1)=2, a(2)=5, a(n+3) = 4*a(n+2) - 5*a(n+1) + 2*a(n). - Hermann Kremer (Hermann.Kremer(AT)online.de), Mar 16 2004

%F a(n) = A000225(n) + n. - _Zerinvary Lajos_, May 29 2009

%F E.g.f.: U(0), where U(k) = 1 + x/(2^k + 2^k/(x - 1 - x^2*2^(k+1)/(x*2^(k+1) - (k+1)/U(k+1) )));(continued fraction, 3rd kind, 4-step ). - _Sergei N. Gladkovskii_, Dec 01 2012

%F G.f.: G(0)*x/(1-x) where G(k) = 1 + 2^k/(1 - x/(x + 2^k/G(k+1) )); (continued fraction). - _Sergei N. Gladkovskii_, May 24 2013

%F G.f.: Q(0)*x/(1-x), where Q(k)= 1 + 1/(2^k - 2*x*4^k/(2*x*2^k + 1/Q(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, May 24 2013

%F E.g.f.: exp(2*x) - (1-x)*exp(x). - _G. C. Greubel_, Oct 18 2019

%e a(3) = 10 because "0001110100" has length 10 and contains all possible patterns of 3 bits:

%e   0001110100

%e   ----------

%e   000.......

%e   .001......

%e   ......010.

%e   ..011.....

%e   .......100

%e   .....101..

%e   ....110...

%e   ...111....

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

%p seq(2^n + n-1, n=0..40); # _G. C. Greubel_, Oct 18 2019

%t Table[2^n+n-1, {n,0,40}] (* _Vladimir Joseph Stephan Orlovsky_, Oct 25 2008 *)

%o (Magma) [2^n + n - 1: n in [0..40]]; // _Vincenzo Librandi_, Jun 20 2011

%o (PARI) a(n)=2^n+n-1 \\ _Charles R Greathouse IV_, Nov 20 2011

%o (Sage) [2^n +n-1 for n in (0..40)] # _G. C. Greubel_, Oct 18 2019

%o (GAP) List([0..40], n-> 2^n +n-1); # _G. C. Greubel_, Oct 18 2019

%Y Cf. A000051, A000215, A160692.

%K easy,nonn

%O 0,2

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