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

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?

• This kinda looks like a de Bruijn sequence, maybe there is a similar construction method? Mar 5, 2022 at 15:09

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