login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A282212 Number of maximal squarefree words of length n over the alphabet {0,1,2}. 3
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, 444, 528, 690, 966, 1236, 1602, 2112, 2712, 3522, 4818, 6150, 8094, 10452, 13854, 17784, 23082, 29970, 39438, 51030, 66792, 86502, 113064, 147036, 191952, 249390 (list; graph; refs; listen; history; text; internal format)
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

Cf. A006156.

Sequence in context: A260712 A173066 A173452 * A074591 A318877 A035321

Adjacent sequences:  A282209 A282210 A282211 * A282213 A282214 A282215

KEYWORD

nonn,more

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 8 10:04 EDT 2022. Contains 356009 sequences. (Running on oeis4.)