login
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).
5

%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