%I #59 Aug 14 2022 15:30:17
%S 1,12,121,1213,12131,121312,1213121,12131231,121312313,1213123132,
%T 12131231321,121312313212,1213123132123,12131231321231,
%U 121312313212312,1213123132123121,12131231321231213,121312313212312131,1213123132123121312,12131231321231213123,121312313212312131231
%N 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).
%C If no insertion can make a squarefree word then the sequence terminates.
%C 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).
%C Sequence was inspired by the sequence A351386.
%H Michael S. Branicky, <a href="/A332603/b332603.txt">Table of n, a(n) for n = 1..1000</a>
%H Jaroslaw Grytczuk, Hubert Kordulewski, and Artur Niewiadomski, <a href="https://doi.org/10.37236/9264">Extremal Square-Free Words</a>, Electronic J. Combinatorics, 27 (1), 2020, #1.48.
%e 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
%t 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 *)
%o (Python)
%o from itertools import islice
%o def issquarefree(s):
%o for l in range(1, len(s)//2 + 1):
%o for i in range(len(s)-2*l+1):
%o if s[i:i+l] == s[i+l:i+2*l]: return False
%o return True
%o def nexts(s):
%o for k in range(len(s)+1):
%o for c in "123":
%o w = s + c if k == 0 else s[:-k] + c + s[-k:]
%o if issquarefree(w): return w
%o def agen(s="1"):
%o while s != None: yield int(s); s = nexts(s)
%o print(list(islice(agen(), 21))) # _Michael S. Branicky_, Aug 12 2022
%Y Cf. A332604, A351386.
%K nonn
%O 1,2
%A _N. J. A. Sloane_, Mar 07 2020
%E Name edited by and more terms from _Giovanni Resta_, Mar 09 2020
%E Edited by _N. J. A. Sloane_, Mar 20 2022
%E Name clarified by _Bartlomiej Pawlik_, Aug 12 2022