# 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