login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A052944 a(n) = 2^n + n - 1. 21
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
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
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.
Eric Weisstein's World of Mathematics, Cyclotomic Polynomial
Eric Weisstein's World of Mathematics, Coin Tossing
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
Sequence in context: A065613 A249557 A061705 * A132736 A263366 A068035
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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 26 13:41 EST 2024. Contains 370352 sequences. (Running on oeis4.)