login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A166316 Lexicographically largest binary de Bruijn sequences, B(2,n). 9
2, 12, 232, 63056, 4221224224, 18295693635288736320, 338921575014037816709507133224870496384, 115563265193225535967792084153637585725267224878335215248443107599191173632256 (list; graph; refs; listen; history; text; internal format)
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.

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

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

Sequence in context: A182507 A348877 A309615 * A011840 A296462 A125804

Adjacent sequences: A166313 A166314 A166315 * A166317 A166318 A166319

KEYWORD

base,nonn

AUTHOR

Darse Billings, Oct 11 2009

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 5 08:15 EST 2023. Contains 360082 sequences. (Running on oeis4.)