OFFSET
1,6
COMMENTS
This sequence counts "occurrences" of (possibly identical) squares, overlaps allowed. See Kucherov et al. link. - Michael S. Branicky, Dec 20 2020
LINKS
G. Kucherov, P. Ochem and M. Rao, How many square occurrences must a binary sequence contain?, Electronic Journal of Combinatorics V. 10 (2003), paper #R12.
EXAMPLE
a(4) = 1 because every string of length > 3 contains at least one square and 0100 contains only one square.
PROG
(Python)
from itertools import product
def count_overlaps(subs, s):
c = i = 0
while i != -1:
i = s.find(subs, i)
if i != -1: c += 1; i += 1
return c
def a(n):
if n == 1: return 0
squares = ["".join(u) + "".join(u)
for r in range(1, n//2 + 1) for u in product("01", repeat = r)]
words = ("0"+"".join(w) for w in product("10", repeat=n-1))
themin = n*n
for w in words:
numw = 0
for s in squares:
numw += count_overlaps(s, w)
if numw >= themin: break
else: themin = min(themin, numw)
return themin
print([a(n) for n in range(1, 21)]) # Michael S. Branicky, Dec 20 2020
CROSSREFS
KEYWORD
nonn,hard,more
AUTHOR
Jeffrey Shallit, Apr 07 2005
STATUS
approved