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

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, 4016, 4908, 5948, 7278, 8868, 10844, 13278, 16230, 19826, 24208, 29554, 36088, 44030, 53808, 65744, 80316, 98052, 119742, 146124

Offset

0,2

Links

Michael S. Branicky, Table of n, a(n) for n = 0..75

Juhani Karhumäki and Jeffrey Shallit, Polynomial vs Exponential Growth in Repetition-Free Binary Words, arXiv:math/0304095 [math.CO], 2003.

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.

Formula

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

Prog

(Python)
from fractions import Fraction
from functools import lru_cache
from itertools import count, islice, product
def period(x):
    for p in range(1, len(x)):
        if all(x[i] == x[i+p] for i in range(len(x)-p)):
            return p
    return len(x)
def exp(x):
    return Fraction(len(x), period(x))
@lru_cache(maxsize=None)
def cexp(x):
    if len(x) == 1: return 1
    return max(exp(x), cexp(x[:-1]), cexp(x[1:]))
def agen(): # generator of 7/3+-power-free terms
    yield 1
    stfs = set("0")
    for n in count(1):
        yield 2*len(stfs)
        stfsnew = set(s+i for s in stfs for i in "01" if cexp(s+i) <= Fraction(7, 3))
        stfs = stfsnew
print(list(islice(agen(), 40))) # Michael S. Branicky, Dec 08 2025

Crossrefs

Cf. A038952, A028445, A007777, A082379.

Sequence in context: A103257 A103259 A280131 * A238871 A323595 A136460

Adjacent sequences: A082377 A082378 A082379 * A082381 A082382 A082383

Keyword

nonn

Author

Ralf Stephan, Apr 10 2003

Extensions

Changed name by Jeffrey Shallit, Sep 26 2014

a(29) and onward from Michael S. Branicky, Dec 08 2025

Status

approved