%I #92 Mar 15 2023 18:32:45
%S 1,2,4,6,10,16,24,36,56,80,118,174,254,378,554,802,1168,1716,2502,
%T 3650,5324,7754,11320,16502,24054,35058,51144,74540,108664,158372,
%U 230800,336480,490458,714856,1041910,1518840,2213868,3226896,4703372,6855388,9992596
%N Number of cubefree words of length n on two letters.
%C It appears that the number of maximal cubefree words A282133(n) ~ a(n-11). - _M. F. Hasler_, May 05 2017
%D S. R. Finch, Mathematical Constants, Cambridge, 2003, see page 368 for cubefree words.
%H Michael S. Branicky, <a href="/A028445/b028445.txt">Table of n, a(n) for n = 0..60</a> (terms 0..47 entered by Charles R Greathouse IV from Edlin paper)
%H Anne E. Edlin, <a href="http://www.math.temple.edu/~anne/cubefree.html">Cubefree words</a> [Broken link]
%H Anne E. Edlin, <a href="/A028445/a028445.pdf">Cubefree words</a> [Cached copy, pdf version, with permission]
%H Anne E. Edlin, <a href="/A028445/a028445_1.pdf">The number of binary cubefree words of length up to 47 and their numerical analysis</a> [Cached copy, with permission]
%H Anne E. Edlin, <a href="/A028445/a028445.txt">Maple package "Cubefree"</a> [Cached copy, with permission]
%H Anne E. Edlin, <a href="/A028445/a028445_1.txt">Maple package "GJseries"</a> [Cached copy, with permission]
%H Mari Huova, <a href="http://www.doria.fi/handle/10024/95677">Combinatorics on Words. New Aspects on Avoidability, Defect Effect, Equations and Palindromes</a>, Turku Centre for Computer Science, TUCS Dissertations No 172, April 2014.
%H K. Jarhumaki and J. Shallit, <a href="https://arxiv.org/abs/math/0304095">Polynomial vs Exponential Growth in Repetition-Free Binary Words</a>, arXiv:math/0304095 [math.CO], 2003.
%H R. Kolpakov, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL10/Kolpakov/kolpakov42.html">Efficient Lower Bounds on the Number of Repetition-free Words</a>, J. Integer Sequences, Vol. 10 (2007), Article 07.3.2.
%H A. M. Shur, <a href="http://dx.doi.org/10.1016/j.cosrev.2012.09.001">Growth properties of power-free languages</a>, Computer Science Review, Vol. 6 (2012), 187-208.
%H A. M. Shur, <a href="http://arxiv.org/abs/1009.4415">Numerical values of the growth rates of power-free languages</a>, arXiv:1009.4415 [cs.FL], 2010.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CubefreeWord.html">Cubefree Word.</a>
%F 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
%p isCubeFree:=proc(v) local n,L;
%p for n from 3 to nops(v) do for L to n/3 do
%p if v[n-L*2+1 .. n] = v[n-L*3+1 .. n-L] then RETURN(false) fi od od; true end;
%p A028445:=proc(n) local s,m;
%p if n=0 then 1 else add( `if`(isCubeFree(convert(m,base,2)),2,0), m = 2^(n-1)..2^n-1) fi end;
%p [seq(A028445(n),n=0..10)]; # _M. F. Hasler_, May 04 2017
%t Length/@NestList[DeleteCases[Flatten[Outer[Append, #, {0, 1}, 1], 1], {___, x__, x__, x__, ___}] &, {{}}, 20] (* _Vladimir Reshetnikov_, May 16 2016 *)
%o (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
%o (Python)
%o from itertools import product
%o def cf(s):
%o for l in range(1, len(s)//3 + 1):
%o for i in range(len(s) - 3*l + 1):
%o if s[i:i+l] == s[i+l:i+2*l] == s[i+2*l:i+3*l]: return False
%o return True
%o def a(n):
%o if n == 0: return 1
%o return 2*sum(1 for w in product("01", repeat=n-1) if cf("0"+"".join(w)))
%o print([a(n) for n in range(21)]) # _Michael S. Branicky_, Mar 13 2022
%o (Python) # faster, but > memory, version for initial segment of sequence
%o def icf(s): # incrementally cubefree
%o for l in range(1, len(s)//3 + 1):
%o if s[-3*l:-2*l] == s[-2*l:-l] == s[-l:]: return False
%o return True
%o def aupton(nn, verbose=False):
%o alst, cfs = [1], set("0")
%o for n in range(1, nn+1):
%o an = 2*len(cfs)
%o cfsnew = set(c+i for c in cfs for i in "01" if icf(c+i))
%o alst, cfs = alst+[an], cfsnew
%o if verbose: print(n, an)
%o return alst
%o print(aupton(30)) # _Michael S. Branicky_, Mar 13 2022
%Y Cf. A007777, A082379, A082380, A286262.
%Y A282133 gives the maximally cubefree words.
%K nonn
%O 0,2
%A Anne Edlin (anne(AT)euclid.math.temple.edu)
%E a(29)-a(36) from _Lars Blomberg_, Aug 22 2013