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$

Improve this question
$\endgroup$
2
  • $\begingroup$ What's the proof that there is at least one such sequence for all $n\geq 2$? $\endgroup$
    – kodlu
    Commented 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$
    – Manfred Weis
    Commented Apr 2, 2016 at 6:41

2 Answers 2

Reset to default
5
$\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.

Improve this answer
$\endgroup$
8
$\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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .