A166315 - OEIS

%I #49 Feb 16 2025 08:33:11

%S 1,3,23,2479,73743071,151050438420815295,

%T 1360791906900646753867474206897715071,

%U 228824044090659455778900855050322128002759787305348791014476408721956007679

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

%C Term a(n) is a cyclical bit string of length 2^n, with every possible substring of length n occurring exactly once.

%C 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)."

%C Terms grow like Theta(2^(2^n)). - _Darse Billings_, Oct 18 2009

%H William Boyles, <a href="/A166315/b166315.txt">Table of n, a(n) for n = 1..11</a> (first 9 terms from Darse Billings)

%H Darse Billings, <a href="/A166315/a166315.py.txt">Python program</a>

%H Frank Ruskey, <a href="http://combos.org/necklace">Necklaces, Lyndon words, De Bruijn sequences, etc.</a>

%H Frank Ruskey, <a href="/A000011/a000011.pdf">Necklaces, Lyndon words, De Bruijn sequences, etc.</a> [Cached copy, with permission, pdf format only]

%H Frank Ruskey, <a href="https://page.math.tu-berlin.de/~felsner/SemWS17-18/Ruskey-Comb-Gen.pdf">Combinatorial Generation</a> (pdf, 2003).

%H SageMath, <a href="https://github.com/sagemath/sage/blob/develop/src/sage/combinat/debruijn_sequence.pyx">Python code</a>

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/deBruijnSequence.html">de Bruijn Sequence</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/De_Bruijn_sequence">de Bruijn Sequence</a>

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

%o (Python) # See Links.

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

%K base,nonn

%O 1,2

%A _Darse Billings_, Oct 11 2009

%E a(6)-a(8) from _Darse Billings_, Oct 18 2009