This site is supported by donations to The OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A052944 a(n) = 2^n + n - 1. 17
 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 (list; graph; refs; listen; history; text; internal format)
 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, 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 T. Manneville, V. Pilaud, Compatibility fans for graphical nested complexes, arXiv preprint arXiv:1501.07152, 2015 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) = 4a(n+2) - 5a(n+1) + 2a(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 EXAMPLE a(3)=10 because "0001110100" has length 10 and contains all possible patterns of 3 bits. MAPLE spec := [S, {S=Prod(Union(Sequence(Union(Z, Z)), Sequence(Z)), Sequence(Z))}, unlabeled ]: seq(combstruct[count ](spec, size=n), n=0..20); MATHEMATICA Table[2^n+n-1, {n, 0, 100}] (* 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 CROSSREFS Cf. A000215, A000051, 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

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

Last modified May 25 23:54 EDT 2019. Contains 323576 sequences. (Running on oeis4.)