A332603 Working over the alphabet {1,2,3}, start with a(1) = 1; then a(n+1) is made by inserting a letter into a(n) at the rightmost possible position which makes a squarefree word (and the smallest letter if multiple letters are possible at that place).

1, 12, 121, 1213, 12131, 121312, 1213121, 12131231, 121312313, 1213123132, 12131231321, 121312313212, 1213123132123, 12131231321231, 121312313212312, 1213123132123121, 12131231321231213, 121312313212312131, 1213123132123121312, 12131231321231213123, 121312313212312131231

Offset: 1

Author

N. J. A. Sloane, Mar 07 2020

Keywords

• nonn

Comments

If no insertion can make a squarefree word then the sequence terminates.

Grytczuk et al. (2020) conjecture that this process never terminates. They also conjecture a(n) converges to a certain infinite word (the beginning of which is now given in A332604).

Sequence was inspired by the sequence A351386.

Examples

			Squarefree a(8) = 12131231 is in the sequence because following extensions of a(7) = 1213121 are not squarefree: 1213121(1), 1213121(2), 1213121(3), 121312(1)1, 121312(2)1. - _Bartlomiej Pawlik_, Aug 12 2022
		

Links

• Michael S. Branicky, Table of n, a(n) for n = 1..1000
• Jaroslaw Grytczuk, Hubert Kordulewski, and Artur Niewiadomski, Extremal Square-Free Words, Electronic J. Combinatorics, 27 (1), 2020, #1.48.

Crossrefs

Cf. A332604, A351386.

Programs

Mathematica

sqfQ[str_] := StringFreeQ[str, x__ ~~ x__]; ext[s_] := Catch@ Block[{t}, Do[ If[sqfQ[t = StringInsert[s, e, -p]], Throw@ t], {p, StringLength[s] + 1}, {e, {"1", "2", "3"} } ]]; a[1]=1; a[n_] := a[n] = ToExpression@ ext@ ToString@ a[n-1]; Array[a, 21] (* Giovanni Resta, Mar 09 2020 *)

Python

from itertools import islice
def issquarefree(s):
    for l in range(1, len(s)//2 + 1):
        for i in range(len(s)-2*l+1):
            if s[i:i+l] == s[i+l:i+2*l]: return False
    return True
def nexts(s):
    for k in range(len(s)+1):
        for c in "123":
            w = s + c if k == 0 else s[:-k] + c + s[-k:]
            if issquarefree(w): return w
def agen(s="1"):
    while s != None: yield int(s); s = nexts(s)
print(list(islice(agen(), 21))) # Michael S. Branicky, Aug 12 2022

Extensions

Name edited by and more terms from Giovanni Resta, Mar 09 2020

Edited by N. J. A. Sloane, Mar 20 2022

Name clarified by Bartlomiej Pawlik, Aug 12 2022