A166315 Lexicographically earliest binary de Bruijn sequences, B(2,n).

1, 3, 23, 2479, 73743071, 151050438420815295, 1360791906900646753867474206897715071, 228824044090659455778900855050322128002759787305348791014476408721956007679

Offset

1,2

Comments

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

Links

William Boyles, Table of n, a(n) for n = 1..11 (first 9 terms from Darse Billings)

Darse Billings, Python program

Mathworld, de Bruijn Sequence

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]

Wikipedia, de Bruijn Sequence

Example

Example: For n = 3, the first de Bruijn sequence, a(n) = B(2,3), is '00010111' = 23.

Crossrefs

Cf. A166316 (Lexicographically largest de Bruijn sequences (binary complements)).

Sequence in context: A351107 A009818 A210734 * A371346 A347680 A113577

Adjacent sequences: A166312 A166313 A166314 * A166316 A166317 A166318

Keyword

base,nonn

Author

Darse Billings, Oct 11 2009

Extensions

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

Status

approved