|
%I #20 Dec 21 2020 01:52:55
%S 0,0,0,1,1,2,2,2,3,4,4,5,5,6,6,7,7,8,8,9,10,10,11,11,12,12,13,13,14,
%T 15,15,16,16,17,17,18,18,19,20,20
%N Minimum number of squares (repeated adjacent nonempty subwords) in a binary string of length n.
%C This sequence counts "occurrences" of (possibly identical) squares, overlaps allowed. See Kucherov et al. link. - _Michael S. Branicky_, Dec 20 2020
%H G. Kucherov, P. Ochem and M. Rao, <a href="https://doi.org/10.37236/1705">How many square occurrences must a binary sequence contain?</a>, Electronic Journal of Combinatorics V. 10 (2003), paper #R12.
%e a(4) = 1 because every string of length > 3 contains at least one square and 0100 contains only one square.
%o (Python)
%o from itertools import product
%o def count_overlaps(subs, s):
%o c = i = 0
%o while i != -1:
%o i = s.find(subs, i)
%o if i != -1: c += 1; i += 1
%o return c
%o def a(n):
%o if n == 1: return 0
%o squares = ["".join(u) + "".join(u)
%o for r in range(1, n//2 + 1) for u in product("01", repeat = r)]
%o words = ("0"+"".join(w) for w in product("10", repeat=n-1))
%o themin = n*n
%o for w in words:
%o numw = 0
%o for s in squares:
%o numw += count_overlaps(s, w)
%o if numw >= themin: break
%o else: themin = min(themin, numw)
%o return themin
%o print([a(n) for n in range(1, 21)]) # _Michael S. Branicky_, Dec 20 2020
%K nonn,hard,more
%O 1,6
%A _Jeffrey Shallit_, Apr 07 2005
|
