A166315 -id:A166315 - cp's OEIS frontend

A166316 Lexicographically largest binary de Bruijn sequences, B(2,n).

2, 12, 232, 63056, 4221224224, 18295693635288736320, 338921575014037816709507133224870496384, 115563265193225535967792084153637585725267224878335215248443107599191173632256

Offset: 1

Darse Billings, Oct 11 2009

Term a(n) is a cyclical bit string of length 2^n, with every possible substring of length n occurring exactly once.
Mathworld says: "Every de Bruijn sequence corresponds to an Eulerian cycle on a de Bruijn graph. Surprisingly, it turns out that the lexicographic sequence of Lyndon words of lengths divisible by n gives the lexicographically earliest de Bruijn sequence (Ruskey). de Bruijn sequences can be generated by feedback shift registers (Golomb 1967; Ronse 1984; Skiena 1990, p. 196)."
Terms grow like Theta(2^(2^n)). - Darse Billings, Oct 18 2009

			For n = 3, the last de Bruijn sequence, a(n) = B(2,3), is '11101000' = 232.

Darse Billings, Table of n, a(n) for n=1..9
Darse Billings, Python program
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
Eric Weisstein's World of Mathematics, de Bruijn Sequence
Wikipedia, de Bruijn Sequence

Cf. A166315 (lexicographically earliest de Bruijn sequences (binary complements)).

a(6)-a(8) from Darse Billings, Oct 18 2009

A327232 Smallest integer k such that the set of all n consecutive digits of k equals the set of 0 to 2^n-1 written as n-digit binary numbers.

Original entry on oeis.org

10, 10011, 1000101110, 1000010011010111100, 100000100011001010011101011011111000, 100000010000110001010001110010010110011010011110101011101101111110000

Offset: 1

Jinyuan Wang, Oct 26 2019

nonn

floor(a(n)/10^(n-1)) is the juxtaposition of a de Bruijn sequence. [This is because the first and last n-1 digits of a(n) are always identical - see my link for a general proof. - Jianing Song, Oct 29 2019]

			For n = 2, the set of all n consecutive digits of 10011 is {10, 00, 01, 11} and the set of 0 to 2^n-1 in binary is {00, 01, 10, 11}.
For n = 3, the set of all n consecutive digits of 1000101110 is {100, 000, 001, 010, 101, 011, 111, 110} and the set of 0 to 2^n-1 in binary is {000, 001, 010, 011, 100, 101, 110, 111}.

Jianing Song, A general proof that the first and last n-1 digits of a(n) are identical
Eric Weisstein's World of Mathematics, de Bruijn Sequence
Wikipedia, de Bruijn Sequence

Cf. A007088, A166315 (earliest binary de Bruijn sequences), A166316 (largest binary de Bruijn sequences), A327233 (largest k).

a(n) = {my(v=vector(2^n), w=vector(2^n)); k=2^(2^n+n-2)-1; for(i=1, 2^n, v[i]=fromdigits(binary(i-1))); while(Set(w)!=v, u=binary(k++); w[1]=fromdigits(u)\10^(2^n-1); for(i=2, 2^n, w[i]=u[i+n-1]+10*(w[i-1]%10^(n-1)))); fromdigits(u); }

a(n) = A007088(A166315(n))*10^(n-2) + 10^(2^n+n-2) for n > 1. Proof: by the property mentioned in the comment section, write a(n) = (d_1)*10^(2^n+n-2) + (d_2)*10^(2^n+n-3) + ... + (d_2^n)*10^(n-1) + (d_1)*10^(n-2) + (d_2)*10^(n-3) + ... + (d_(n-1))*10^0, d_i = 0 or 1, then d_1 = 1, (d_2)*2^(2^n-1) + (d_3)*2^(2^n-2) + ... + (d_2^n)*2^1 + (d_1)*2^0 >= A166315(n), and d_2, d_3, ..., d_(n-1) >= 0. The equalities can hold simultaneously (when written as a 2^n-digit binary number, A166315(n) begins with n 0's and ends with a 1), which gives the formula. - Jianing Song, Oct 28 2019

a(n) = A004086(floor(A327233(n)/10^(n-2)))*10^(n-2) for n > 1. - Jinyuan Wang, Nov 02 2019

a(5)-a(6) from Jinyuan Wang, Nov 02 2019

A308831 Start with generation 0, which is the empty sequence. For generation N>=1, extend the existing sequence into a non-cyclic ternary de Bruijn sequence of order N. If more than one extension is possible, choose the lexicographically earliest.

Original entry on oeis.org

0, 1, 2, 0, 0, 2, 2, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 2, 1, 0, 2, 0, 2, 1, 2, 2, 2, 0, 1, 0, 0, 1, 1, 0, 1, 0, 2, 1, 0, 0, 2, 0, 0, 0, 0, 2, 1, 1, 1, 1, 0, 2, 2, 0, 0, 1, 2, 1, 1, 2, 0, 1, 1, 2, 2, 0, 2, 0, 1, 2, 2, 1, 2, 1, 2, 0, 2, 2, 2, 2, 1, 0, 1, 2

Offset: 0

A. D. Skovgaard, Jun 27 2019

nonn

If using a binary alphabet instead, it would not be possible to extend the sequence infinitely as a de Bruijn sequence (order 3 needs an extra term: 01100010111). - A. D. Skovgaard, Apr 19 2020

			Generation 1:
[012] (All ternary sequences of length 1 now appear. With 3! = 6 solutions, the lexicographically earliest is chosen.)
Generation 2:
[0120022110] (The sequence is extended from the previous generation, now including all ternary sequences of length 2.)
The process continues.

A. D. Skovgaard, Table of n, a(n) for n = 0..246
A. D. Skovgaard, Python program to generate the sequence, with explanatory comments
A. D. Skovgaard, a(n) for n = 0..246 in compressed notation

Cf. A080679 (binary equivalent), A166315, A169676.

A327233 Largest integer k < 10^(2^n+n) such that the set of all n consecutive digits of k equals the set of 0 to 2^n-1 written as n-digit binary numbers.

Original entry on oeis.org

10, 11001, 1110100011, 1111011001010000111, 111110111001101011000101001000001111, 111111011110011101011100011011010011001011000010101000100100000011111

Offset: 1

Jinyuan Wang, Oct 26 2019

nonn

floor(a(n)/10^(n-1)) is the juxtaposition of a de Bruijn sequence. [This is because the first and last n-1 digits of a(n) are always identical - see my link for a general proof. - Jianing Song, Oct 29 2019]

Jianing Song, A general proof that the first and last n-1 digits of a(n) are identical
Eric Weisstein's World of Mathematics, de Bruijn Sequence
Wikipedia, de Bruijn Sequence

Cf. A007088, A166315 (earliest binary de Bruijn sequences), A166316 (largest binary de Bruijn sequences), A327232 (smallest k).

a(n) = A004086(A327232(n))*10^(n-2) + A002275(n-2) for n > 1.
a(n) = A007088(A166316(n))*10^(n-1) + A002275(n-1).
Proof: by the property mentioned in the comment section, write a(n) = (d_1)*10^(2^n+n-2) + (d_2)*10^(2^n+n-3) + ... + (d_2^n)*10^(n-1) + (d_1)*10^(n-2) + (d_2)*10^(n-3) + ... + (d_(n-1))*10^0, d_i = 0 or 1, then (d_1)*2^(2^n-1) + (d_2)*2^(2^n-2) + ... + (d_2^n)*2^0 <= A166316(n), and d_1, d_2, ..., d_(n-1) <= 1. The equalities can hold simultaneously (when written as a 2^n-digit binary number, A166316(n) begins with n 1's), which gives the formula. - Jianing Song, Oct 28 2019

A144569 A de Bruijn sequence B(4,3) found by Ted Bell.

Original entry on oeis.org

0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 2, 0, 2, 2, 2, 1, 2, 1, 1, 2, 2, 0, 0, 3, 0, 3, 3, 3, 2, 3, 2, 2, 3, 3, 1, 3, 1, 1, 3, 3, 0, 1, 3, 2, 0, 3, 2, 1, 0, 3, 1, 0, 2, 3, 1, 2, 0, 1, 2, 3, 0, 2, 1, 3, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 2, 0, 2, 2, 2, 1, 2, 1, 1, 2, 2, 0, 0, 3, 0, 3, 3, 3, 2, 3, 2, 2, 3, 3, 1

Offset: 0

N. J. A. Sloane, Apr 09 2010, based on a communication from David Paterson (David.Paterson(AT)csiro.au)

			Period 64: 0001110100202221211220030333232233131133013203210310231201230213

Mark Dow, Minimal arrays containing all sub-array combinations of symbols: de Bruijn sequences and tori (Web archive)
Wikipedia, De Bruijn Sequences
Index entries for linear recurrences with constant coefficients, order 64.

A135472 gives an example of a B(9,2).

Cf. also A080679, A058342, A083570, A166315, A166316.

A246536 a(n) = number of strings (including the empty string) over an alphabet of size n that do not have any substrings of length > 1 that appear more than once in the string.

Original entry on oeis.org

3, 25, 1885, 3636297, 327094648711

Offset: 1

Peter M. Huggins, Aug 28 2014

Here "substrings" have no "gaps", i.e. a substring means a subsequence of characters from the original string using contiguous indices.

The number of De Bruijn sequences B(n,2) (which has a known explicit formula) can be used to give the fairly tight lower bound that a(n) > 2*n^2*B(n,2). See A166315.

Cf. A166315.

cp's OEIS Frontend

A166316 Lexicographically largest binary de Bruijn sequences, B(2,n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A327232 Smallest integer k such that the set of all n consecutive digits of k equals the set of 0 to 2^n-1 written as n-digit binary numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A308831 Start with generation 0, which is the empty sequence. For generation N>=1, extend the existing sequence into a non-cyclic ternary de Bruijn sequence of order N. If more than one extension is possible, choose the lexicographically earliest.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A327233 Largest integer k < 10^(2^n+n) such that the set of all n consecutive digits of k equals the set of 0 to 2^n-1 written as n-digit binary numbers.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A144569 A de Bruijn sequence B(4,3) found by Ted Bell.

Views

Author

Keywords

Examples

Links

Crossrefs

A246536 a(n) = number of strings (including the empty string) over an alphabet of size n that do not have any substrings of length > 1 that appear more than once in the string.

Views

Author

Keywords

Comments

Crossrefs