OFFSET
0,2
COMMENTS
a(n), n > 0, is a multiple of 4 by symmetry. - Michael S. Branicky, Jun 20 2022
LINKS
A. M. Shur, Growth properties of power-free languages, Computer Science Review, Vol. 6 (2012), 187-208.
A. M. Shur, Numerical values of the growth rates of power-free languages, arXiv:1009.4415 [cs.FL], 2010.
Eric Weisstein's World of Mathematics, Squarefree Word.
FORMULA
Let L be the limit lim a(n)^{1/n}, which exists because a(n) is a submultiplicative sequence. Then L=2.6215080... (Shur 2010). See (Shur 2012) for the methods of estimating such limits. - Arseny Shur, Apr 26 2015
EXAMPLE
There are 96 quaternary squarefree words of length 4: each of the words 0102, 0120, 0121, 0123 has 4!=24 images under the permutations of the set {0,1,2,3}. - Arseny Shur, Apr 26 2015
G.f. = 1 + 4*x + 12*x^2 + 36*x^3 + 96*x^4 + 264*x^5 + 696*x^6 + 1848*x^7 + ....
PROG
(Python)
def isf(s): # incrementally squarefree (check factors ending in last letter)
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 = [1], set("1")
for n in range(1, nn+1):
an = 4*len(sfs)
sfsnew = set(s+i for s in sfs for i in "0123" if isf(s+i))
alst, sfs = alst+[an], sfsnew
if verbose: print(n, an)
return alst
print(aupton(14)) # Michael S. Branicky, Jun 20 2022
CROSSREFS
KEYWORD
nonn
AUTHOR
EXTENSIONS
More terms from David Wasserman, Feb 27 2002
a(13)-a(15) from John W. Layman, Mar 03 2004
a(16)-a(25) from Max Alekseyev, Jul 03 2006
a(26)-a(30) from Giovanni Resta, Mar 20 2020
STATUS
approved