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