A273154 Number of 4-power-free binary words of length n.

1, 2, 4, 8, 14, 26, 48, 88, 160, 292, 532, 972, 1768, 3220, 5866, 10686, 19454, 35430, 64528, 117520, 214004, 389724, 709730, 1292496, 2353758, 4286442, 7806048, 14215620, 25888034, 47144704, 85855230, 156350996, 284730756, 518523184, 944282620

Offset

0,2

Comments

A 4-power-free binary word is a word over the alphabet {0, 1} that cannot be represented as a concatenation XYYYYZ, where Y is a nonempty word, but X and Z may be empty.

A028445(n) <= a(n) <= A135491(n).

Links

Table of n, a(n) for n=0..34.

Mathematica

Length/@NestList[DeleteCases[Flatten[Outer[Append, #, {0, 1}, 1], 1], {___, x__, x__, x__, x__, ___}] &, {{}}, 16]

Prog

(Python)
from itertools import product
def qf(s):
    for l in range(1, len(s)//4 + 1):
      for i in range(len(s) - 4*l + 1):
          if s[i:i+l] == s[i+l:i+2*l] == s[i+2*l:i+3*l] == s[i+3*l:i+4*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 qf("0"+"".join(w)))
print([a(n) for n in range(21)]) # Michael S. Branicky, Mar 14 2022
(Python) # faster, but > memory, version for initial segment of sequence
def iqf(s): # incrementally 4th-power free
    for l in range(1, len(s)//4 + 1):
        if s[-4*l:-3*l] == s[-3*l:-2*l] == s[-2*l:-l] == s[-l:]:
            return False
    return True
def aupton(nn, verbose=False):
    alst, qfs = [1], set("0")
    for n in range(1, nn+1):
        an = 2*len(qfs)
        qfsnew = set(q+i for q in qfs for i in "01" if iqf(q+i))
        alst, qfs = alst+[an], qfsnew
        if verbose: print(n, an)
    return alst
print(aupton(20)) # Michael S. Branicky, Mar 14 2022

Crossrefs

Cf. A028445, A135491.

Sequence in context: A305003 A117633 A308148 * A135491 A164154 A164156

Adjacent sequences: A273151 A273152 A273153 * A273155 A273156 A273157

Keyword

nonn,more

Author

Vladimir Reshetnikov, May 16 2016

Extensions

a(17)-a(30) from Lars Blomberg, Nov 11 2017

a(31)-a(34) from Michael S. Branicky, Mar 14 2022

Status

approved