OFFSET
1,7
COMMENTS
A word is "squarefree" if it contains no nonempty block of the form xx.
A squarefree word w is maximal if wa contains a square for all symbols a.
The structure of such words was described by Li (1976). - Jeffrey Shallit, Jan 16 2019
a(n) is a multiple of 3 by symmetry. - Michael S. Branicky, Jul 21 2021
LINKS
Michael S. Branicky, Table of n, a(n) for n = 1..62
Shuo-Yen R. Li, Annihilators in nonrepetitive semigroups, Studies in Applied Math. 55 (1976), 83-85.
EXAMPLE
For n = 7 the maximal squarefree words are 0102010 and the 5 others induced by permuting the symbols.
MAPLE
extend:= proc(w) local res, t, wt, i;
res:= NULL;
for t from "0" to "2" do
wt:= cat(w, t);
if andmap(i -> wt[-2*i..-i-1] <> wt[-i..-1], [$1..floor(length(wt)/2)]) then res:= wt, res fi
od:
res
end proc:
L[1]:= ["0"]:
for n from 1 to 43 do
A[n]:= 0: L[n+1]:= NULL;
for t in L[n] do
r:= extend(t);
if [r] = [] then A[n]:= A[n]+3
else L[n+1]:= L[n+1], r
fi
od;
L[n+1]:= [L[n+1]];
od:
seq(A[n], n=1..43); # Robert Israel, Feb 09 2017
PROG
(Python)
def isf(s): # incrementally squarefree
for l in range(1, len(s)//2 + 1):
if s[-2*l:-l] == s[-l:]: return False
return True
def aupton(nn, verbose=False):
alst, sfs = [], set("0")
for n in range(1, nn+1):
an, sfsnew = 0, set()
for s in sfs:
se = [s+i for i in "012" if isf(s+i)]
if len(se) > 0: sfsnew.update(se)
else: an += 3
alst, sfs = alst+[an], sfsnew
if verbose: print(n, an)
return alst
print(aupton(40)) # Michael S. Branicky, Jul 21 2021
CROSSREFS
KEYWORD
nonn
AUTHOR
Jeffrey Shallit, Feb 09 2017
EXTENSIONS
a(37)-a(43) from Robert Israel, Feb 09 2017
a(44) and beyond from Michael S. Branicky, Jul 21 2021
STATUS
approved