cp's OEIS Frontend

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

%I A321168 #29 Feb 14 2023 17:10:59
%S A321168 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,
%T A321168 27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,
%U A321168 50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67
%N A321168 Maximum number of squarefree conjugates of a ternary word of length n.
%C A321168 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.
%C A321168 Conjecture: a(n) = n for n >= 18. - _Michael S. Branicky_, Jul 21 2021
%C A321168 The conjecture is true: see Clokie et al. - _James Rayman_, Feb 14 2023
%H A321168 T. Clokie, D. Gabric and J. Shallit <a href="https://arxiv.org/abs/1904.08187">Circularly squarefree words and unbordered conjugates: a new approach</a>, arXiv:1904.08187 [cs.FL], Apr 2019
%H A321168 <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (2,-1).
%F A321168 a(n) = n for n != 5,7,9,10,14,17. - _James Rayman_, Feb 14 2023
%e A321168 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.
%o A321168 (Python)
%o A321168 from itertools import product
%o A321168 def isf(s): # incrementally squarefree
%o A321168     for l in range(1, len(s)//2 + 1):
%o A321168         if s[-2*l:-l] == s[-l:]: return False
%o A321168     return True
%o A321168 def aupton(nn, verbose=False):
%o A321168     alst, sfs = [], set("012")
%o A321168     for n in range(1, nn+1):
%o A321168         # max(sum(s[i:]+s[:i] in sfs for i in range(len(s))) for s in sfs)
%o A321168         an = 0
%o A321168         for s in sfs:
%o A321168             sfconjs = 0
%o A321168             for i in range(len(s)):
%o A321168                 if s[i:] + s[:i] in sfs: sfconjs += 1
%o A321168             an = max(an, sfconjs)
%o A321168             if an == n: break # short circuit maximum max
%o A321168         sfsnew = set(s+i for s in sfs for i in "012" if isf(s+i))
%o A321168         alst, sfs = alst+[an], sfsnew
%o A321168         if verbose: print(n, an)
%o A321168     return alst
%o A321168 print(aupton(36)) # _Michael S. Branicky_, Jul 21 2021
%Y A321168 Cf. A006156.
%K A321168 nonn,easy
%O A321168 1,2
%A A321168 _Jeffrey Shallit_, Jan 10 2019
%E A321168 a(16)-a(59) from _Michael S. Branicky_, Jul 21 2021