cp's OEIS Frontend

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

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