A007777 -id:A007777 - 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

A082379 Number of length-n 7/3-power-free words over the alphabet {0,1}.

Original entry on oeis.org

1, 2, 4, 6, 10, 14, 20, 24, 30, 40, 48, 56, 64, 76, 82, 92, 106, 124, 142, 152, 172, 192, 210, 220, 234, 256, 284, 308, 314, 332, 356, 372, 392, 420, 456, 488, 524, 560, 588, 608, 640, 684, 736, 764, 796, 832, 874, 892, 912, 948, 994, 1020, 1060, 1112, 1184

Offset: 0

Ralf Stephan, Apr 10 2003

nonn

Juhani Karhumäki and Jeffrey Shallit, Polynomial versus exponential growth in repetition-free binary words, arXiv:math/0304095 [math.CO], April 7 2003.
Juhani Karhumäki and Jeffrey Shallit, Polynomial versus exponential growth in repetition-free binary words, Journal of Combinatorial Theory, Series A 105 (2004) 335-347.

Cf. A038952, A028445, A007777, A082380.

Name changed by Jeffrey Shallit, Sep 26 2014

More terms from Jeffrey Shallit, Jul 17 2021

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

A242430 Decimal expansion of the unforgeable pattern-free binary word constant, a constant mentioned in A003000.

Original entry on oeis.org

2, 6, 7, 7, 8, 6, 8, 4, 0, 2, 1, 7, 8, 8, 9, 1, 1, 2, 3, 7, 6, 6, 7, 1, 4, 0, 3, 5, 8, 4, 3, 0, 2, 5, 5, 2, 5, 5, 5, 0, 5, 9, 8, 9, 7, 9, 9, 3, 4, 8, 4, 5, 3, 2, 0, 7, 6, 3, 1, 1, 8, 8, 8, 5, 1, 1, 2, 1, 4, 9, 3, 7, 7, 8, 5, 2, 3, 2, 7, 6, 2, 8, 5, 3, 5, 4, 4, 7, 6, 2, 2, 3, 8, 5, 6, 1, 3, 6, 8, 4

Offset: 0

Jean-François Alcover, May 14 2014

A binary word (a word over a 2-letter alphabet) is said "unforgeable" if it never matches a left or right shift of itself. The limit lower bound of the number of unforgeable words of length n is (0.26778684...)*2^n.

			0.267786840217889112376671403584302552555...

Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, p. 369.
See more references and links in A003000, which is the main entry for this subject.

Cf. A003000, A006156, A007777, A028445, A045690.

digits = 100; k0 = 5; dk = 5; Clear[r]; r[k_] := r[k] = Sum[(-1)^(n-1)*2/(2^(2^(n+1)-1)-1) * Product[2^(2^m-1)/(2^(2^m-1)-1), {m, 2, n}], {n, 1, k}] // N[#, digits+10]&; r[k0]; r[k = k0 + dk]; While[RealDigits[r[k], 10, digits+10] !=  RealDigits[r[k - dk], 10, digits+10], Print["k = ", k]; k = k + dk]; RealDigits[r[k], 10, digits] // First

A277277 Number of overpal-free binary words of length n.

Original entry on oeis.org

1, 2, 4, 6, 10, 14, 20, 28, 36, 44, 56, 72, 92, 116, 148, 188, 240, 304, 388, 492, 628, 796, 1016, 1288, 1644, 2084, 2660, 3372, 4304, 5456, 6964, 8828, 11268, 14284, 18232, 23112, 29500, 37396, 47732, 60508, 77232, 97904, 124964, 158412, 202196, 256316, 327160, 414728, 529356, 671044, 856516

Offset: 0

Jeffrey Shallit, Oct 08 2016

An "overpal" is a word of the form a x a x^R a, where a is a single letter, x is a (possibly empty) word, and x^R denotes the reverse of the word x. To be "overpal-free" is to contain no factor (contiguous block) that is an overpal.

A binary word avoids overpals if and only if it avoids aaa, ababa, and abbabba as factors (Narad Rampersad). This gives the proof of Barker's formulas below. - Jeffrey Shallit, Oct 09 2016 and Colin Barker, Oct 10 2016

			For n = 4, the 14 words are 00100, 00101, 00110, 01001, and their complements and reversals.

Colin Barker, Table of n, a(n) for n = 0..1000
Aayush Rajasekaran, Narad Rampersad, Jeffrey Shallit, Overpals, Underlaps, and Underpals, In: Brlek S., Dolce F., Reutenauer C., Vandomme É. (eds) Combinatorics on Words, WORDS 2017, Lecture Notes in Computer Science, vol 10432.
Index entries for linear recurrences with constant coefficients, signature (0,1,0,1).

Cf. A007777.

Vec((1+2*x+3*x^2+4*x^3+5*x^4+6*x^5+6*x^6+8*x^7+6*x^8+2*x^9)/(1-x^2-x^4) + O(x^50)) \\ Colin Barker, Oct 10 2016

From Colin Barker, Oct 08 2016: (Start)
a(n) = a(n-2)+a(n-4) for n>9.
G.f.: (1+2*x+3*x^2+4*x^3+5*x^4+6*x^5+6*x^6+8*x^7+6*x^8+2*x^9) / (1-x^2-x^4).
(End)

A356959 Number of length-n binary strings that can be infinitely extended to the right to form an overlap-free string.

Original entry on oeis.org

2, 4, 6, 10, 14, 18, 22, 26, 32, 36, 40, 44, 48, 52, 58, 64, 72, 76, 80, 84, 88, 92, 98, 102, 106, 110, 114, 120, 128, 134, 142, 150, 160, 164, 168, 172, 176, 180, 186, 190, 194, 198, 202, 208, 216, 220, 228, 232, 236, 240, 244, 248, 252, 258, 266, 274, 284

Offset: 1

Jeffrey Shallit, Sep 06 2022

nonn

A binary string is overlap-free if it contains no block of the form axaxa, where a in {0,1} and x a possibly empty string.

			For example, 010011001011010010 is infinitely extendable to the right, but 010011001011010011 is not (every extension by a word of length 7 gives an overlap).

Y. Kobayashi, Enumeration of irreducible binary words, Discrete Applied Mathematics 20 (1988), 221-232.
L. Schaeffer and J. Shallit, The first-order theory of binary overlap-free words is decidable, arXiv:2209.03266 [cs.FL], 2022.

Cf. A007777.

a(n) = Theta(n^c), where c = 1.15501186367066470321... .

A368707 Number of length-n overlap-free binary words that are squares.

Original entry on oeis.org

0, 2, 0, 2, 0, 6, 0, 4, 0, 0, 0, 12, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 24, 0, 0, 0, 0, 0, 0, 0, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 48, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 1

Jeffrey Shallit, Jan 04 2024

			The overlap-free words of length 6 are  001001, 010010, 011011, 001011, 001100, 001101, 010011, 010110, 011001, 011010, and their binary complements, but only the first 3 are squares.

Cf. A007777.

a(2) = 2; a(2^n) = 2^{n-1} for n>=2; a(3*2^n) = 3*2^n for n>=1; a(n) = 0 for all other entries.

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

A082379 Number of length-n 7/3-power-free words over the alphabet {0,1}.

Views

Author

Keywords

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A242430 Decimal expansion of the unforgeable pattern-free binary word constant, a constant mentioned in A003000.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

Mathematica

A277277 Number of overpal-free binary words of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A356959 Number of length-n binary strings that can be infinitely extended to the right to form an overlap-free string.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A368707 Number of length-n overlap-free binary words that are squares.

Views

Author

Keywords

Examples

Crossrefs

Formula