Hints for efficient computation of the maximum length of a binary sequence

Question

Given a positive integer $n$ I would like to compute $f(n)$, the maximum possible length of a binary sequence such that any substring of it (subsequence with consecutive elements), of length $n$, never repeats.

For example, with $n = 1$, I have a maximum length of $2$, obtained with $(0, 1)$ or $(1, 0)$.

For $n=2$ I think the maximum should be $5$, which I can obtain with the sequence $(0,0,1,1,0)$.

Similarly, I can get a length of at least $9$ for $n=3$ and $15$ for $n=4$ with the sequences $(0,0,0,1,0,1,1,0,1)$ and $(0,0,0,0,1,0,0,1,1,0,1,1,1,0,1)$ respectively.

Obviously I can write an exhaustive search with a number of operations proportional to $2^{f(n)}$, but this starts to be impractical already for $n=6$.

Any hint for reducing the time complexity? Is it possible in the first place?

Answer 1

I think that $f(n) = 2^n + n - 1$. To construct a word of length $f(n)$ with no repeated substring of length $n$, pick $\beta_n$ the $n$-th de Bruijn sequence over the alphabet $\{0, 1\}$ (of length $2^n$), and add the first $n-1$ letters of $\beta_n$ at the end.

Here's some examples:

• for $n = 2$, pick $(0, 0, 1, 1, 0)$;
• for $n = 3$, $(0,0,0,1,0,1,1,1,0,0)$ of length $10$ (and not $9$ as you suggested);
• for $n = 4$, $(0,0,0,0,1,0,0,1,1,0,1,0,1,1,1,1,0,0,0)$ of length $19$ (and not $15$ as you suggested).

The construction of $\beta_{n+1}$ is obtnained by constructing a directed graph $G_n = (V_n, E_n)$ such that:

• $V_n = \{0,1\}^n$ (vertices are words of length $n$);
• for $u=u_1u_2…u_n, v=v_1v_2…v_n\in V_n$, there is an edge labelled by $v_n$ from $u$ to $v$ if and only if $u_2…u_n = v_1…v_{n-1}$.

A candidate (there are multiple possibilities) for the word $\beta_{n+1}$ is then the word obtained by reading edge's labels in an eulerian cycle.

To prove that $f(n)$ is indeed equal to $2^n+n-1$:

• $f(n) \geqslant 2^n+n-1$ since the word constructed above has no repeated substring of length $n$ (because $\beta_n$ has no repeated circular substring of length $n$);
• $f(n) \leqslant 2^n+n-1$ since there are $2^n$ different substring of length $n$, so there cannot be more than $2^n$ positions in the word that can be the beginning of a substring of length $n$.