login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A028445 Number of cubefree words of length n on two letters. 20

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 00:26 EDT 2024. Contains 371264 sequences. (Running on oeis4.)