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,2

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.

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.

Example

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

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

Prog

(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

Crossrefs

Cf. A332604, A351386.

Sequence in context: A037543 A214317 A037487 * A358615 A231869 A038490

Adjacent sequences: A332600 A332601 A332602 * A332604 A332605 A332606

Keyword

nonn

Author

N. J. A. Sloane, Mar 07 2020

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

Status

approved