login
This site is supported by donations 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. 16
1, 2, 4, 6, 10, 16, 24, 36, 56, 80, 118, 174, 254, 378, 554, 802, 1168, 1716, 2502, 3650, 5324, 7754, 11320, 16502, 24054, 35058, 51144, 74540, 108664, 158372, 230800, 336480, 490458, 714856, 1041910, 1518840, 2213868 (list; graph; refs; listen; history; text; internal format)
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

Charles R Greathouse IV, Table of n, a(n) for n = 0..47 [copied 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

CROSSREFS

Cf. A007777, A082379, A082380, A286262.

A282133 gives the maximally cubefree words.

Sequence in context: A132002 A098151 A211971 * A006305 A067247 A017985

Adjacent sequences:  A028442 A028443 A028444 * A028446 A028447 A028448

KEYWORD

nonn

AUTHOR

Anne Edlin (anne(AT)euclid.math.temple.edu)

EXTENSIONS

a(29)-a(36) from Lars Blomberg, Aug 22 2013

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified July 27 22:07 EDT 2017. Contains 289866 sequences.