MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

A binary De Bruijn sequence of index $n$ is a circular sequence $S=a_1 a_2 \dots a_{2^n},$ with $a_i \in \{0,1\},$ and such that each of the $2^n$ binary $n$-uples occurs exactly once in $S.$

Is there an infinite binary sequence $b_1 b_2 b_3 \dots$ such that $b_1 \dots b_{2^n}$ is a binary De Bruijn Sequence of index $n$ for all $n$ ?

share|cite|improve this question
WLOG the sequence starts 01. Now the first four terms have to be 0110. But this can never be part of an index 3 De Bruijn sequence, because an index 3 De Bruijn sequence has to have precisely four 1s and three of them had better be consecutive, but this can't happen with a 0110. So, sadly, the answer is "no". – Kevin Buzzard Jun 11 '11 at 18:20
Are there at least interesting subsequences $n_1,n_2,\ldots$ of the natural numbers so that $b_1b2_\ldots b_{2^{n_i}}$ is a binary De Bruijn sequence for each $n_i$? For example, can this work if $n_i=2^i$? – Simon Jul 9 '11 at 13:08
up vote 1 down vote accepted

No. It may as well start with 0 in which case it is forced to be 01 for order 2 and then be 0110 for order 4. In order to include 111 it could only continue to be 01101110 or 01100111 but both of those have 011 twice and miss 000.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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