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

Author

Vladimir Reshetnikov, May 16 2016

Keywords

• nonn
• more

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).

Crossrefs

Cf. A028445, A135491.

Programs

Mathematica

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

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

Extensions

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

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