cp's OEIS Frontend

A282212 Number of maximal squarefree words of length n over the alphabet {0,1,2}.

%I A282212 #25 Apr 06 2023 10:27:00
%S A282212 0,0,0,0,0,0,6,0,0,0,6,6,6,6,24,24,24,36,54,54,120,138,216,240,384,
%T A282212 444,528,690,966,1236,1602,2112,2712,3522,4818,6150,8094,10452,13854,
%U A282212 17784,23082,29970,39438,51030,66792,86502,113064,147036,191952,249390
%N A282212 Number of maximal squarefree words of length n over the alphabet {0,1,2}.
%C A282212 A word is "squarefree" if it contains no nonempty block of the form xx.
%C A282212 A squarefree word w is maximal if wa contains a square for all symbols a.
%C A282212 The structure of such words was described by Li (1976). - _Jeffrey Shallit_, Jan 16 2019
%C A282212 a(n) is a multiple of 3 by symmetry. - _Michael S. Branicky_, Jul 21 2021
%H A282212 Michael S. Branicky, <a href="/A282212/b282212.txt">Table of n, a(n) for n = 1..62</a>
%H A282212 Shuo-Yen R. Li, <a href="https://doi.org/10.1002/sapm197655183">Annihilators in nonrepetitive semigroups</a>, Studies in Applied Math. 55 (1976), 83-85.
%e A282212 For n = 7 the maximal squarefree words are 0102010 and the 5 others induced by permuting the symbols.
%p A282212 extend:= proc(w) local res,t,wt,i;
%p A282212   res:= NULL;
%p A282212   for t from "0" to "2" do
%p A282212     wt:= cat(w,t);
%p A282212     if andmap(i -> wt[-2*i..-i-1] <> wt[-i..-1], [$1..floor(length(wt)/2)]) then res:= wt,res fi
%p A282212   od:
%p A282212 res
%p A282212 end proc:
%p A282212 L[1]:= ["0"]:
%p A282212 for n from 1 to 43 do
%p A282212   A[n]:= 0: L[n+1]:= NULL;
%p A282212   for t in L[n] do
%p A282212     r:= extend(t);
%p A282212     if [r] = [] then A[n]:= A[n]+3
%p A282212     else L[n+1]:= L[n+1],r
%p A282212     fi
%p A282212   od;
%p A282212   L[n+1]:= [L[n+1]];
%p A282212 od:
%p A282212 seq(A[n],n=1..43); # _Robert Israel_, Feb 09 2017
%o A282212 (Python)
%o A282212 def isf(s): # incrementally squarefree
%o A282212     for l in range(1, len(s)//2 + 1):
%o A282212         if s[-2*l:-l] == s[-l:]: return False
%o A282212     return True
%o A282212 def aupton(nn, verbose=False):
%o A282212     alst, sfs = [], set("0")
%o A282212     for n in range(1, nn+1):
%o A282212         an, sfsnew = 0, set()
%o A282212         for s in sfs:
%o A282212             se = [s+i for i in "012" if isf(s+i)]
%o A282212             if len(se) > 0: sfsnew.update(se)
%o A282212             else: an += 3
%o A282212         alst, sfs = alst+[an], sfsnew
%o A282212         if verbose: print(n, an)
%o A282212     return alst
%o A282212 print(aupton(40)) # _Michael S. Branicky_, Jul 21 2021
%Y A282212 Cf. A006156.
%K A282212 nonn
%O A282212 1,7
%A A282212 _Jeffrey Shallit_, Feb 09 2017
%E A282212 a(37)-a(43) from _Robert Israel_, Feb 09 2017
%E A282212 a(44) and beyond from _Michael S. Branicky_, Jul 21 2021