OFFSET
1,1
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
Darse Billings, Table of n, a(n) for n=1..9
Darse Billings, Python program
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
EXAMPLE
For n = 3, the last de Bruijn sequence, a(n) = B(2,3), is '11101000' = 232.
CROSSREFS
KEYWORD
base,nonn
AUTHOR
Darse Billings, Oct 11 2009
EXTENSIONS
a(6)-a(8) from Darse Billings, Oct 18 2009
STATUS
approved