A082379 -id:A082379 - cp's OEIS frontend

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

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, 3226896, 4703372, 6855388, 9992596

Offset: 0

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

nonn

It appears that the number of maximal cubefree words A282133(n) ~ a(n-11). - M. F. Hasler, May 05 2017

S. R. Finch, Mathematical Constants, Cambridge, 2003, see page 368 for cubefree words.

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.

Cf. A007777, A082379, A082380, A286262.

A282133 gives the maximally cubefree words.

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

Length/@NestList[DeleteCases[Flatten[Outer[Append, #, {0, 1}, 1], 1], {_, x__, x__, x__, _}] &, {{}}, 20] (* Vladimir Reshetnikov, May 16 2016 *)

(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<M. F. Hasler, May 04 2017

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

# 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

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

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

A007777 Number of overlap-free binary words of length n.

Original entry on oeis.org

1, 2, 4, 6, 10, 14, 20, 24, 30, 36, 44, 48, 60, 60, 62, 72, 82, 88, 96, 112, 120, 120, 136, 148, 164, 152, 154, 148, 162, 176, 190, 196, 210, 216, 224, 228, 248, 272, 284, 296, 300, 296, 320, 332, 356, 356, 376, 400, 416, 380, 382, 376, 382, 356, 374, 392, 410

Offset: 0

Julien Cassaigne (cassaign(AT)clipper.ens.fr)

J. Cassaigne, Counting overlap-free binary words, pp. 216-225 of STACS '93, Lect. Notes Comput. Sci., Springer-Verlag, 1993.
J. Cassaigne, Motifs évitables et régularités dans les mots (Thèse de Doctorat), Tech. Rep. LITP-TH 94-04, Institut Blaise Pascal, Paris, 1994.
Raphael M. Jungers, Vladimir Yu. Protasov and Vincent D. Blondel, Computing the Growth of the Number of Overlap-Free Words with Spectra of Matrices, in LATIN 2008: Theoretical Informatics, Lecture Notes in Computer Science, Volume 4957/2008, [From N. J. A. Sloane, Jul 10 2009]

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.
Franz-Josef Brandenburg, Uniformly Growing k-th Power-Free Homomorphisms, Theoretical Computer Science, volume 23, 1983, pages 69-82. See density of two letter weakly square-free strings (as overlap-free is called in this paper) after theorem 12 page 80. A misprint omits a(14) = 62 from the list of values.
J. Cassaigne, Counting overlap-free binary words, Preprint. (Annotated scanned copy)
J. Cassaigne, Counting overlap-free binary words
J. Cassaigne, Motifs évitables et régularités dans les mots, Thèse de Doctorat, Paris, 1994.
K. Jarhumaki and J. Shallit, Polynomial vs Exponential Growth in Repetition-Free Binary Words, arXiv:math/0304095 [math.CO], 2003.
Eric Weisstein's World of Mathematics, Overlapfree Word.

Cf. A028445, A038952, A082379, A082380.

delta:=linalg[matrix](4,4,[0,0,1,1,0,0,0,0,0,1,0,0,1,0,0,0]); iota:=linalg[matrix](4,4,[0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0]); kappa:=linalg[matrix](4,4,[0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0]);
V:=proc(n) options remember: if n>7 and n mod 2 =1 then RETURN(evalm(kappa &* V((n+1)/2) &* transpose(delta) + delta &* V((n+1)/2) &* transpose(kappa))) elif n=5 then RETURN(linalg[matrix](4,4,[2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0])) elif n=7 then RETURN(linalg[matrix](4,4,[0,0,2,0,0,2,0,0,2,0,0,0,0,0,0,0])) else RETURN(linalg[matrix](4,4,0)) fi: end;
U:=proc(n) options remember: if n>7 and n mod 2 =1 then RETURN(evalm(iota &* V((n+1)/2) &* transpose(delta) + delta &* V((n+1)/2) &* transpose(iota) + (kappa+iota) &* U((n+1)/2) &* transpose(delta) + delta &* U((n+1)/2) &* transpose(kappa+iota))) elif n>7 and n mod 2 =0 then RETURN(evalm(iota &* V(n/2) &* transpose(iota) + delta &* V(n/2+1) &* transpose(delta) + (kappa+iota) &* U(n/2) &* transpose(kappa+iota) + delta &* U(n/2+1) &* transpose(delta))) elif n=4 then RETURN(linalg[matrix](4,4,[2,0,2,0,0,2,0,0,2,0,0,0,0,0,0,2])) elif n=5 then RETURN(linalg[matrix](4,4,[0,2,2,0,2,0,0,2,2,0,2,0,0,2,0,0])) elif n=6 then RETURN(linalg[matrix](4,4,[2,2,0,2,2,2,2,0,0,2,2,0,2,0,0,2])) elif n=7 then RETURN(linalg[matrix](4,4,[4,2,0,2,2,0,2,2,0,2,0,2,2,2,2,0])) fi: end;
a:=proc(n) if n<4 then RETURN([1,2,4,6][n+1]) else RETURN(add(add(U(n)[i,j],i=1..4),j=1..4)) fi: end; seq(a(n),n=0..100); # Pab Ter (pabrlos2(AT)yahoo.com), Nov 09 2005

delta = {{0, 0, 1, 1}, {0, 0, 0, 0}, {0, 1, 0, 0}, {1, 0, 0, 0}};
iota = {{0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 0}};
kappa = {{0, 0, 1, 1}, {1, 1, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}};
V[n_] := V[n] = Which[n > 7 && Mod[n, 2] == 1, delta . V[(n+1)/2] . Transpose[kappa] + kappa . V[(n+1)/2] . Transpose[delta], n == 5, {{2, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}}, n == 7, {{0, 0, 2, 0}, {0, 2, 0, 0}, {2, 0, 0, 0}, {0, 0, 0, 0}}, True, Array[0& , {4, 4}]];
U[n_] := U[n] = Which[n > 7 && Mod[n, 2] == 1, delta . U[(n+1)/2] . Transpose[iota + kappa] + delta . V[(n+1)/2] . Transpose[iota] + iota . V[(n+1)/2] . Transpose[delta] + (iota + kappa) . U[(n+1)/2] . Transpose[delta], n > 7 && Mod[n, 2] == 0, delta.U[n/2+1] . Transpose[delta] + delta . V[n/2+1] . Transpose[delta] + iota . V[n/2] . Transpose[iota] + (iota + kappa) . U[n/2] . Transpose[iota + kappa], n == 4, {{2, 0, 2, 0}, {0, 2, 0, 0}, {2, 0, 0, 0}, {0, 0, 0, 2}}, n == 5, {{0, 2, 2, 0}, {2, 0, 0, 2}, {2, 0, 2, 0}, {0, 2, 0, 0}}, n == 6, {{2, 2, 0, 2}, {2, 2, 2, 0}, {0, 2, 2, 0}, {2, 0, 0, 2}}, n == 7, {{4, 2, 0, 2}, {2, 0, 2, 2}, {0, 2, 0, 2}, {2, 2, 2, 0}}];
a[n_] := If[n < 4, {1, 2, 4, 6}[[n+1]], Sum[U[n][[i, j]], {i, 1, 4}, {j, 1, 4}]];
Table[a[n], {n, 0, 56}] (* Jean-François Alcover, Jan 02 2013, translated from Pab Ter's Maple program *)

More terms from Pab Ter (pabrlos2(AT)yahoo.com), Nov 09 2005

A082380 Number of 7/3+-power-free words over the alphabet {0,1}.

Original entry on oeis.org

1, 2, 4, 6, 10, 14, 20, 30, 38, 50, 64, 86, 108, 136, 178, 222, 276, 330, 408, 500, 618, 774, 962, 1178, 1432, 1754, 2160, 2660, 3292

Offset: 0

Ralf Stephan, Apr 10 2003

nonn

J. Karhumäki and J. Shallit, Polynomial vs Exponential Growth in Repetition-Free Binary Words
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.

Cf. A038952, A028445, A007777, A082379.

Let L = lim a(n)^(1/n); then L exists since a(n) is submultiplicative. 1.2206318 < L < 1.22064482 (Shur 2012); the gap between the bounds can be made less than any given constant. Empirically, the upper bound is precise: L=1.2206448... . - Arseny Shur, Apr 26 2015

Changed name by Jeffrey Shallit, Sep 26 2014

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Python

Formula

Extensions

A007777 Number of overlap-free binary words of length n.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A082380 Number of 7/3+-power-free words over the alphabet {0,1}.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions