

A166316


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


3



2, 12, 232, 63056, 4221224224, 18295693635288736320, 338921575014037816709507133224870496384, 115563265193225535967792084153637585725267224878335215248443107599191173632256
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

Comment: Term a(n) is a cyclical bit string of length 2^n, with every possible substring of length n occurring exactly once.
Mathworld (http://mathworld.wolfram.com/deBruijnSequence.html) 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)."
Python code available with sequence A166315. [From Darse Billings, Oct 18 2009]
Terms grow like Theta(2^(2^n)).  Darse Billings, Oct 18 2009


LINKS

Darse Billings, Table of n, a(n) for n=1..9
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 last de Bruijn sequence, a(n) = B(2,3), is '11101000' = 232.


CROSSREFS

Cf. A166315 = 1, 3, 23, 2479, 73743071, ..., Lexicographically earliest de Bruijn sequences (binary complements).
Sequence in context: A009359 A011807 A182507 * A011840 A296462 A125804
Adjacent sequences: A166313 A166314 A166315 * A166317 A166318 A166319


KEYWORD

base,nonn


AUTHOR

Darse Billings, Oct 11 2009


EXTENSIONS

Added three more terms, a(6)  a(8) Darse Billings, Oct 18 2009


STATUS

approved



