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.)