I am looking at some code to produce binary cyclic de Bruijn sequences. If $n$ is the length of the subsequence that should not be repeated more than once, it looks for a non-cyclic de Bruijn sequence of length $2^n + n - 1$ and then returns the first $2^n$ bits as the cyclic sequence.
This appears to always give a cyclic de Bruijn sequence but I don't understand why. Why are the last $n-1$ bits of the non-cyclic sequence of length $2^n+n-1$ always the same as the first $n-1$ bits?
Here is the code in Python.
def debruijn(x): if x.find(x[-n:]) < len(x)-n: # check if last n chars occur earlier in the string return if len(x) == N+n-1: print(x[:N]) return debruijn(x+"0") debruijn(x+"1") n = 4 x = "0"*n N = 2**n debruijn(x)
Here is the output for $n=4$.
0000100110101111 0000100111101011 0000101001101111 0000101001111011 [...]
(Originally posted to https://stackoverflow.com/questions/57731516/why-does-this-de-bruijn-code-always-return-0s-for-the-last-few-bits but moved here on request.)