1,2

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 smallest 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

Darse Billings, Table of n, a(n) for n=1..9

Darse Billings, Python program

Mathworld, de BruijnSequence

F. Ruskey, Informationon necklaces, unlabelled necklaces, Lyndon words, de Bruijn sequences

Wikipedia, de BruijnSequence

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

Cf. A166316 = 2, 12, 232, 63056, 4221224224, ..., Lexicographically largest de Bruijn sequences (binary complements).

Sequence in context: A088056 A009593 A009818 this_sequence A113577 A120085 A062834

Adjacent sequences: A166312 A166313 A166314 this_sequence A166316 A166317 A166318

base,nonn

Darse Billings (darse(AT)cs.ualberta.ca), Oct 11 2009

Added three more terms, a(6) - a(8) Darse Billings (darse(AT)cs.ualberta.ca), Oct 18 2009