OFFSET
0,2
COMMENTS
It appears that the number of maximal cubefree words A282133(n) ~ a(n-11). - M. F. Hasler, May 05 2017
REFERENCES
S. R. Finch, Mathematical Constants, Cambridge, 2003, see page 368 for cubefree words.
LINKS
Michael S. Branicky, Table of n, a(n) for n = 0..60 (terms 0..47 entered by Charles R Greathouse IV from Edlin paper)
Anne E. Edlin, Cubefree words [Broken link]
Anne E. Edlin, Cubefree words [Cached copy, pdf version, with permission]
Anne E. Edlin, The number of binary cubefree words of length up to 47 and their numerical analysis [Cached copy, with permission]
Anne E. Edlin, Maple package "Cubefree" [Cached copy, with permission]
Anne E. Edlin, Maple package "GJseries" [Cached copy, with permission]
Mari Huova, Combinatorics on Words. New Aspects on Avoidability, Defect Effect, Equations and Palindromes, Turku Centre for Computer Science, TUCS Dissertations No 172, April 2014.
K. Jarhumaki and J. Shallit, Polynomial vs Exponential Growth in Repetition-Free Binary Words, arXiv:math/0304095 [math.CO], 2003.
R. Kolpakov, Efficient Lower Bounds on the Number of Repetition-free Words, J. Integer Sequences, Vol. 10 (2007), Article 07.3.2.
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, Cubefree Word.
FORMULA
Let L = lim a(n)^(1/n); then L exists since a(n) is submultiplicative, and 1.4575732 < L < 1.4575772869240 (Shur 2010). Empirical: L=1.4575772869237..., i.e. the upper bound is very precise. - Arseny Shur, Apr 27 2015
MAPLE
isCubeFree:=proc(v) local n, L;
for n from 3 to nops(v) do for L to n/3 do
if v[n-L*2+1 .. n] = v[n-L*3+1 .. n-L] then RETURN(false) fi od od; true end;
A028445:=proc(n) local s, m;
if n=0 then 1 else add( `if`(isCubeFree(convert(m, base, 2)), 2, 0), m = 2^(n-1)..2^n-1) fi end;
[seq(A028445(n), n=0..10)]; # M. F. Hasler, May 04 2017
MATHEMATICA
Length/@NestList[DeleteCases[Flatten[Outer[Append, #, {0, 1}, 1], 1], {___, x__, x__, x__, ___}] &, {{}}, 20] (* Vladimir Reshetnikov, May 16 2016 *)
PROG
(PARI) (isCubeFree(v)=!for(n=3, #v, for(L=1, n\3, v[n-L*2+1..n]==v[n-L*3+1..n-L]&&return))); A028445(n)=sum(m=1<<(n-1)+1<<(n-4), 1<<n-1<<(n-3)-1, isCubeFree(binary(m)))<<!!n \\ Becomes slow beyond n=20. - M. F. Hasler, May 04 2017
(Python)
from itertools import product
def cf(s):
for l in range(1, len(s)//3 + 1):
for i in range(len(s) - 3*l + 1):
if s[i:i+l] == s[i+l:i+2*l] == s[i+2*l:i+3*l]: return False
return True
def a(n):
if n == 0: return 1
return 2*sum(1 for w in product("01", repeat=n-1) if cf("0"+"".join(w)))
print([a(n) for n in range(21)]) # Michael S. Branicky, Mar 13 2022
(Python) # faster, but > memory, version for initial segment of sequence
def icf(s): # incrementally cubefree
for l in range(1, len(s)//3 + 1):
if s[-3*l:-2*l] == s[-2*l:-l] == s[-l:]: return False
return True
def aupton(nn, verbose=False):
alst, cfs = [1], set("0")
for n in range(1, nn+1):
an = 2*len(cfs)
cfsnew = set(c+i for c in cfs for i in "01" if icf(c+i))
alst, cfs = alst+[an], cfsnew
if verbose: print(n, an)
return alst
print(aupton(30)) # Michael S. Branicky, Mar 13 2022
CROSSREFS
KEYWORD
nonn,changed
AUTHOR
Anne Edlin (anne(AT)euclid.math.temple.edu)
EXTENSIONS
a(29)-a(36) from Lars Blomberg, Aug 22 2013
STATUS
approved