cp's OEIS Frontend

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

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