A052944 a(n) = 2^n + n - 1.

0, 2, 5, 10, 19, 36, 69, 134, 263, 520, 1033, 2058, 4107, 8204, 16397, 32782, 65551, 131088, 262161, 524306, 1048595, 2097172, 4194325, 8388630, 16777239, 33554456, 67108889, 134217754, 268435483, 536870940, 1073741853, 2147483678

Offset

0,2

Comments

Shortest length of bit-string containing all bit-strings of given length n. - Rainer Rosenthal, Apr 30 2003

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

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

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

a(n) = A006127(n) - 1. - Reinhard Zumkeller, Apr 13 2011

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

References

Discussed in newsgroup de.rec.denksport in Apr 2003

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

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Adam M. Goyt and Lara K. Pudwell, Avoiding colored partitions of two elements in the pattern sense, arXiv preprint arXiv:1203.3786 [math.CO], 2012; J. Int. Seq. 15 (2012) # 12.6.2.

A. M. Hinz, S. Klavžar, U. Milutinović, C. Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 178. Book's website

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1001

Viktor Lopatkin, Pasha Zusmanovich, Commutative Lie algebras and commutative cohomology in characteristic 2, arXiv:1907.03690 [math.KT], 2019.

T. Manneville, V. Pilaud, Compatibility fans for graphical nested complexes, arXiv preprint arXiv:1501.07152 [math.CO], 2015-2016.

E. H. Rivals, Autocorrelation of Strings.

Eric Weisstein's World of Mathematics, Cyclotomic Polynomial

Eric Weisstein's World of Mathematics, Coin Tossing

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

Formula

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

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

For n>=1: partial sums of A000051. - Emeric Deutsch, Mar 04 2004

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

a(n) = A000225(n) + n. - Zerinvary Lajos, May 29 2009

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

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

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

E.g.f.: exp(2*x) - (1-x)*exp(x). - G. C. Greubel, Oct 18 2019

Example

a(3) = 10 because "0001110100" has length 10 and contains all possible patterns of 3 bits:
  0001110100
  ----------
  000.......
  .001......
  ......010.
  ..011.....
  .......100
  .....101..
  ....110...
  ...111....

Maple

spec:= [S, {S=Prod(Union(Sequence(Union(Z, Z)), Sequence(Z)), Sequence(Z))}, unlabeled ]: seq(combstruct[count ](spec, size=n), n=0..20);
seq(2^n + n-1, n=0..40); # G. C. Greubel, Oct 18 2019

Mathematica

Table[2^n+n-1, {n, 0, 40}] (* Vladimir Joseph Stephan Orlovsky, Oct 25 2008 *)

Prog

(Magma) [2^n + n - 1: n in [0..40]]; // Vincenzo Librandi, Jun 20 2011
(PARI) a(n)=2^n+n-1 \\ Charles R Greathouse IV, Nov 20 2011
(Sage) [2^n +n-1 for n in (0..40)] # G. C. Greubel, Oct 18 2019
(GAP) List([0..40], n-> 2^n +n-1); # G. C. Greubel, Oct 18 2019

Crossrefs

Cf. A000051, A000215, A160692.

Sequence in context: A065613 A249557 A061705 * A132736 A263366 A068035

Adjacent sequences: A052941 A052942 A052943 * A052945 A052946 A052947

Keyword

easy,nonn

Author

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

Status

approved