login
Minimum number of squares (repeated adjacent nonempty subwords) in a binary string of length n.
1

%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