# The longest string of none consecutive repeated pattern

Construct a string by using only n characters, the string should do not contain any consecutive repeated pattern, in other words, the string must have not any substring matching /(.+)\1/, what is the length l(n) of the longest string S(n)?

n    S(n)    l(n)
1    a       1
2    aba     3
3    ?       ?
4    ?       ?


Edit:
abcabacbabcabacabcac has none consecutive repeated pattern,so l(3)>=20

-
Could you explain the code? In your example "aba", it seems that "a" is repeated. – damiano Aug 26 '10 at 9:16
Another way to say this is that there are no identical consecutive substrings. – Dan Brumleve Aug 26 '10 at 9:30

A theorem of Thue's (not Thue's theorem!) states that for $n = 3$ (and therefore, also for larger $n$) an infinite sequence of characters (chosen out of $n$) without repeated sub-sequences (a.k.a square-free) exists.

Edit: here's a slightly related reference: J.D. Currie's paper 'There are ternary circular square-free words of length n for n 18.', which at least has a reference to Thue's paper from 1906.

Edit 2: Another reference, with explicit construction of sequences of length 3, 9, 27 and so on: http://arxiv.org/abs/0712.0139. That paper gives the following sequence of length 27: 123213231213123132312132123

-

Let me apologize, for it's not an answer, but merely an extended comment. I like the problem very much. It sounds very classical, and most likely the answer must be known.

Being reformulated, the problem is as follows: if $X$ is an $n$-letter alphabet, we have a rewriting rule $$w_1 s s w_2=w_1 s^2 w_2 \to w_1 w_2$$ where $s$ is nonempty and at least one of $w_1,w_2$ must be nonempty. (In effect, any word that satisfies the condition set by a-boy must be square-free so to speak.) One can also a semigroup with $n$ generators whose relations are determined by the rewriting rule above.

The problem as set asks whether all words over $X$ are reduced to words of certain length $l(n).$ One wonders, however, whether $n=2$ is an exceptional case, and actually there are arbitrary large reduced words. For instance, the following word of length 68 in letters $0,1,2$ is reduced:

12012101201020120212012101202101210201202120121012010201202120121012

For a 4-letter alphabet it is easy to find words of quite large length (I've found by means of computing such words of lenght $\ge 1000.$)

-
Haven't seen the answer by yatima2975 (please see below), when writing my comment. He confirmed my suspitions that there must be reduced words of arbitrary large length when $|X| \ge 3.$ – Olod Aug 26 '10 at 13:22

To find a maximal string for n letters, add a new letter in every other place of a maximal string for n-1 letters. It is still the case that no consecutive identical substrings exist. No more letters can be added because two of them would have to appear consecutively, so this is the best that is possible. The length of the string is 2^n-1.