cp's OEIS Frontend

A028445 Number of cubefree words of length n on two letters.

%I A028445 #93 Feb 16 2025 08:32:35
%S A028445 1,2,4,6,10,16,24,36,56,80,118,174,254,378,554,802,1168,1716,2502,
%T A028445 3650,5324,7754,11320,16502,24054,35058,51144,74540,108664,158372,
%U A028445 230800,336480,490458,714856,1041910,1518840,2213868,3226896,4703372,6855388,9992596
%N A028445 Number of cubefree words of length n on two letters.
%C A028445 It appears that the number of maximal cubefree words A282133(n) ~ a(n-11). - _M. F. Hasler_, May 05 2017
%D A028445 S. R. Finch, Mathematical Constants, Cambridge, 2003, see page 368 for cubefree words.
%H A028445 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 A028445 Anne E. Edlin, <a href="http://www.math.temple.edu/~anne/cubefree.html">Cubefree words</a> [Broken link]
%H A028445 Anne E. Edlin, <a href="/A028445/a028445.pdf">Cubefree words</a> [Cached copy, pdf version, with permission]
%H A028445 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 A028445 Anne E. Edlin, <a href="/A028445/a028445.txt">Maple package "Cubefree"</a> [Cached copy, with permission]
%H A028445 Anne E. Edlin, <a href="/A028445/a028445_1.txt">Maple package "GJseries"</a> [Cached copy, with permission]
%H A028445 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 A028445 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 A028445 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 A028445 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 A028445 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 A028445 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/CubefreeWord.html">Cubefree Word.</a>
%F A028445 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 A028445 isCubeFree:=proc(v) local n,L;
%p A028445 for n from 3 to nops(v) do for L to n/3 do
%p A028445 if v[n-L*2+1 .. n] = v[n-L*3+1 .. n-L] then RETURN(false) fi od od; true end;
%p A028445 A028445:=proc(n) local s,m;
%p A028445 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 A028445 [seq(A028445(n),n=0..10)];  # _M. F. Hasler_, May 04 2017
%t A028445 Length/@NestList[DeleteCases[Flatten[Outer[Append, #, {0, 1}, 1], 1], {___, x__, x__, x__, ___}] &, {{}}, 20] (* _Vladimir Reshetnikov_, May 16 2016 *)
%o A028445 (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 A028445 (Python)
%o A028445 from itertools import product
%o A028445 def cf(s):
%o A028445     for l in range(1, len(s)//3 + 1):
%o A028445       for i in range(len(s) - 3*l + 1):
%o A028445           if s[i:i+l] == s[i+l:i+2*l] == s[i+2*l:i+3*l]: return False
%o A028445     return True
%o A028445 def a(n):
%o A028445     if n == 0: return 1
%o A028445     return 2*sum(1 for w in product("01", repeat=n-1) if cf("0"+"".join(w)))
%o A028445 print([a(n) for n in range(21)]) # _Michael S. Branicky_, Mar 13 2022
%o A028445 (Python) # faster, but > memory, version for initial segment of sequence
%o A028445 def icf(s): # incrementally cubefree
%o A028445     for l in range(1, len(s)//3 + 1):
%o A028445         if s[-3*l:-2*l] == s[-2*l:-l] == s[-l:]: return False
%o A028445     return True
%o A028445 def aupton(nn, verbose=False):
%o A028445     alst, cfs = [1], set("0")
%o A028445     for n in range(1, nn+1):
%o A028445         an = 2*len(cfs)
%o A028445         cfsnew = set(c+i for c in cfs for i in "01" if icf(c+i))
%o A028445         alst, cfs = alst+[an], cfsnew
%o A028445         if verbose: print(n, an)
%o A028445     return alst
%o A028445 print(aupton(30)) # _Michael S. Branicky_, Mar 13 2022
%Y A028445 Cf. A007777, A082379, A082380, A286262.
%Y A028445 A282133 gives the maximally cubefree words.
%K A028445 nonn
%O A028445 0,2
%A A028445 Anne Edlin (anne(AT)euclid.math.temple.edu)
%E A028445 a(29)-a(36) from _Lars Blomberg_, Aug 22 2013