login
Number of 4-power-free binary words of length n.
0

%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