A323487 Number of length-n ternary words that are bi-maximally squarefree.

0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 6, 0, 18, 0, 24, 0, 48, 42, 18, 12, 48, 78, 36, 66, 108, 102, 240, 222, 360, 330, 696, 690, 858, 1086, 1692, 1920, 2604, 3156, 4284, 5370, 7308, 9270, 12036, 15756, 20688, 26562, 34500, 44274, 59058, 75576

Offset

1,7

Comments

A word is squarefree if it contains no block of the form XX, where X is a nonempty block. A word is bi-maximally squarefree if it cannot be extended on either the left or right to a longer squarefree word.

All terms are multiples of 6 due to possible renamings of letters. - Michael S. Branicky, Sep 01 2021

Links

Table of n, a(n) for n=1..58.

Example

For n = 7 the six possibilities are 0102010 and all renamings of the letters.
For n = 15 the six possibilities are 010210120102101 and all renamings of the letters.

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 is_bmsf(w, sfsnew): # is w bi-maximally squarefree
    lefts, rights = [c+w for c in "123"], [w+c for c in "123"]
    return all(x not in sfsnew for x in lefts + rights)
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))
        an = len([w for w in sfs if is_bmsf(w, sfsnew)])
        alst.append(an)
        sfs = sfsnew
    return alst
print(aupton(30)) # Michael S. Branicky, Sep 01 2021

Crossrefs

Cf. A282212, which is the one-sided version of maximally squarefree.

Sequence in context: A307382 A339629 A331428 * A173453 A340979 A102638

Adjacent sequences: A323484 A323485 A323486 * A323488 A323489 A323490

Keyword

nonn

Author

Jeffrey Shallit, Jan 16 2019

Extensions

a(31)-a(58) from Michael S. Branicky, Sep 01 2021

Status

approved