login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A343436
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}.
1
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, 13, 14, 14, 14, 15, 14, 15, 16, 15, 14, 15, 15, 15, 16, 16, 16, 17, 17, 17, 18, 18, 18, 19, 19, 19, 19, 19, 19
OFFSET
3,1
LINKS
Jarosław Grytczuk, Hubert Kordulewski, and Bartłomiej Pawlik, Square-free extensions of words, arXiv:2104.04841 [math.CO], 2021. See Table 2 p. 9.
PROG
(Python)
def isf(w): # incrementally squarefree (check factors ending in last letter)
for l in range(1, len(w)//2 + 1):
if w[-2*l:-l] == w[-l:]: return False
return True
def AE(w, sfsnew): # number of square free extensions of w
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))
def aupton(nn):
alst, sfs = [], set("123")
for n in range(1, nn+1):
sfsnew = set(w+c for w in sfs for c in "123" if isf(w+c))
if n >= 3: alst.append(max(AE(w, sfsnew) for w in sfs))
sfs = sfsnew
return alst
print(aupton(30)) # Michael S. Branicky, Aug 31 2021
CROSSREFS
Cf. A343435.
Sequence in context: A120962 A355922 A261024 * A186282 A171909 A199079
KEYWORD
nonn,more
AUTHOR
Michel Marcus, Apr 15 2021
EXTENSIONS
a(19)-a(50) edited to match Grytczuk et al. reference and a(51)-a(59) from Michael S. Branicky, Aug 31 2021
STATUS
approved