5
$\begingroup$

For $n \ge 2$, there is at least one binary DeBruijn sequence beginning with $n$ zeros followed by $n$ ones. Is there a straightforward way to construct such a sequence for each $n \ge 2$? Examples:

$n=2: 0011$

$n=3: 00011101$

$n=4: 0000111101100101$

$n=5: 00000111110111001101011000101001$

$\endgroup$
2
  • $\begingroup$ What's the proof that there is at least one such sequence for all $n\geq 2$? $\endgroup$
    – kodlu
    Apr 2, 2016 at 3:05
  • $\begingroup$ the proof are the lexically minimal De Bruijn sequences constructed as described here. In the lexical ordering a maximal contiguous sequence of $0$-bits is adjacent to maximal sequence of $1$-bits after making the sequence cyclic. Cutting the cyclic sequence in the right place and adjusting the direction gives the sought sequences. $\endgroup$ Apr 2, 2016 at 6:41

2 Answers 2

4
$\begingroup$

The answer is the construction of the De Bruijn sequence by concatenating certain Lyndon words as indicated here or, in this article; that construction also guarantees the existence of the specific De Bruijn sequences you are looking for.

A very comprehensible hands on explanation of the construction can found here.

$\endgroup$
7
$\begingroup$

One of the simple ways to generate De Bruijn sequenceis the following rule. You write $n$ zeros, and after that "$1$ is better than $0$" (left hand rule): $$0000111101100101000$$ For example 9th digit is $0$ because we already have $1111$. This algorithm was taken from the article N. M. Korobov, "Concerning some questions of uniform distribution". In the article Normal periodic systems and their applications to the estimation of sums of fractional parts he proposed a more general algorithm which allows to generate all possible De Bruijn sequenceis.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.