A321168 Maximum number of squarefree conjugates of a ternary word of length n.

1, 2, 3, 4, 3, 6, 5, 8, 4, 6, 11, 12, 13, 10, 15, 16, 11, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67

Offset

1,2

Comments

Two words are conjugate if one is a cyclic shift of the other. A word is squarefree if it contains no block of the form XX, where X is any nonempty block.

Conjecture: a(n) = n for n >= 18. - Michael S. Branicky, Jul 21 2021

The conjecture is true: see Clokie et al. - James Rayman, Feb 14 2023

Links

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

T. Clokie, D. Gabric and J. Shallit Circularly squarefree words and unbordered conjugates: a new approach, arXiv:1904.08187 [cs.FL], Apr 2019

Index entries for linear recurrences with constant coefficients, signature (2,-1).

Formula

a(n) = n for n != 5,7,9,10,14,17. - James Rayman, Feb 14 2023

Example

For n = 9 the ternary word 012010212 is squarefree, as are three other conjugates of it:  {120102120, 201021201, 010212012}, and this is maximal for length 9.

Prog

(Python)
from itertools import product
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("012")
    for n in range(1, nn+1):
        # max(sum(s[i:]+s[:i] in sfs for i in range(len(s))) for s in sfs)
        an = 0
        for s in sfs:
            sfconjs = 0
            for i in range(len(s)):
                if s[i:] + s[:i] in sfs: sfconjs += 1
            an = max(an, sfconjs)
            if an == n: break # short circuit maximum max
        sfsnew = set(s+i for s in sfs for i in "012" if isf(s+i))
        alst, sfs = alst+[an], sfsnew
        if verbose: print(n, an)
    return alst
print(aupton(36)) # Michael S. Branicky, Jul 21 2021

Crossrefs

Cf. A006156.

Sequence in context: A126801 A076945 A074792 * A341313 A341312 A347123

Adjacent sequences: A321165 A321166 A321167 * A321169 A321170 A321171

Keyword

nonn,easy

Author

Jeffrey Shallit, Jan 10 2019

Extensions

a(16)-a(59) from Michael S. Branicky, Jul 21 2021

Status

approved