%I #17 Mar 14 2022 11:32:18
%S 1,2,4,8,14,26,48,88,160,292,532,972,1768,3220,5866,10686,19454,35430,
%T 64528,117520,214004,389724,709730,1292496,2353758,4286442,7806048,
%U 14215620,25888034,47144704,85855230,156350996,284730756,518523184,944282620
%N Number of 4-power-free binary words of length n.
%C 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.
%C A028445(n) <= a(n) <= A135491(n).
%t Length/@NestList[DeleteCases[Flatten[Outer[Append, #, {0, 1}, 1], 1], {___, x__, x__, x__, x__, ___}] &, {{}}, 16]
%o (Python)
%o from itertools import product
%o def qf(s):
%o for l in range(1, len(s)//4 + 1):
%o for i in range(len(s) - 4*l + 1):
%o 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]:
%o return False
%o return True
%o def a(n):
%o if n == 0: return 1
%o return 2*sum(1 for w in product("01", repeat=n-1) if qf("0"+"".join(w)))
%o print([a(n) for n in range(21)]) # _Michael S. Branicky_, Mar 14 2022
%o (Python) # faster, but > memory, version for initial segment of sequence
%o def iqf(s): # incrementally 4th-power free
%o for l in range(1, len(s)//4 + 1):
%o if s[-4*l:-3*l] == s[-3*l:-2*l] == s[-2*l:-l] == s[-l:]:
%o return False
%o return True
%o def aupton(nn, verbose=False):
%o alst, qfs = [1], set("0")
%o for n in range(1, nn+1):
%o an = 2*len(qfs)
%o qfsnew = set(q+i for q in qfs for i in "01" if iqf(q+i))
%o alst, qfs = alst+[an], qfsnew
%o if verbose: print(n, an)
%o return alst
%o print(aupton(20)) # _Michael S. Branicky_, Mar 14 2022
%Y Cf. A028445, A135491.
%K nonn,more
%O 0,2
%A _Vladimir Reshetnikov_, May 16 2016
%E a(17)-a(30) from _Lars Blomberg_, Nov 11 2017
%E a(31)-a(34) from _Michael S. Branicky_, Mar 14 2022