A343436 - OEIS

%I #12 Aug 31 2021 06:18:29

%S 6,7,6,6,6,6,6,6,6,7,7,7,8,8,8,9,9,9,10,10,10,11,11,11,12,12,12,13,13,

%T 13,14,14,14,15,14,15,16,15,14,15,15,15,16,16,16,17,17,17,18,18,18,19,

%U 19,19,19,19,19

%N Maximum value of the number of different squarefree extensions for words of length n in the set of all finite squarefree words over the alphabet A3 = {1,2,3}.

%H Jarosław Grytczuk, Hubert Kordulewski, and Bartłomiej Pawlik, <a href="https://arxiv.org/abs/2104.04841">Square-free extensions of words</a>, arXiv:2104.04841 [math.CO], 2021.  See Table 2 p. 9.

%o (Python)

%o def isf(w): # incrementally squarefree (check factors ending in last letter)

%o     for l in range(1, len(w)//2 + 1):

%o         if w[-2*l:-l] == w[-l:]: return False

%o     return True

%o def AE(w, sfsnew): # number of square free extensions of w

%o     return len(set(x for x in (w[:i]+c+w[i:] for c in "123" for i in range(len(w)+1)) if x in sfsnew))

%o def aupton(nn):

%o     alst, sfs = [], set("123")

%o     for n in range(1, nn+1):

%o         sfsnew = set(w+c for w in sfs for c in "123" if isf(w+c))

%o         if n >= 3: alst.append(max(AE(w, sfsnew) for w in sfs))

%o         sfs = sfsnew

%o     return alst

%o print(aupton(30)) # _Michael S. Branicky_, Aug 31 2021

%Y Cf. A343435.

%K nonn,more

%O 3,1

%A _Michel Marcus_, Apr 15 2021

%E a(19)-a(50) edited to match Grytczuk et al. reference and a(51)-a(59) from _Michael S. Branicky_, Aug 31 2021