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

Author

Jeffrey Shallit, Jan 10 2019

Keywords

• nonn
• easy

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

Examples

			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.
		

Links

• 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).

Crossrefs

Cf. A006156.

Programs

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

Formula

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

Extensions

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