When will a string have a repeating substring?

Question

What's the minimum number M such that any string with M elements taking values from 1 to N will have a substring repeating itself at least 2 times in a row? The case where N=2 is trivial, you have M=4: 1212 for example the substring 12 repeats itself 2 times in a row, or 1111 where the substring 1 reapeats itself 4 times in a row. It's difficult to find the number even for N=3...

Answer 1

As requested in the comments...

Words of the desired type are said to be "square free". As the OP correctly observes, for binary strings there aren't many instances. $0,1,01,10,101,010$ are the only examples. Somewhat surprisingly, however, even for ternary strings there are infinitely long examples. Wikipedia has a good survey here

Perhaps the simplest, and so far as I know the first, example of an infinite square free ternary word was produced by Thue. It begins with the so-called Thue-Morse binary string, obtained by starting with either character and then successively appending the complement of what's come before. Thus:

$$1,\;10,\;1001,\;10010110,\;1001011001101001,\dots$$

Thue's square free example is then derived from this by taking successive differences. Thus:

$$-1,0,1,-1,1,0,-1,\dots$$

References for these and related results can be found in the Wikipedia article linked to earlier. The proof that the difference sequence of the Thue-Morse word is square free is somewhat lengthy, but it isn't difficult. A good reference for that can be found here.