%I #33 Jan 09 2021 00:42:18
%S 1,2,2,2,2,3,3,3,3,3,3,4,4,4,4,5,5,5,5
%N Maximum, over all binary strings w of length n, of the size of the smallest string attractor for w.
%C A set S of positions of a string w[1..n] is called a "string attractor" if every nonempty contiguous block occurring in w has an occurrence in w that touches at least one of the positions of S. For example, "alfalfa" has a string attractor of size 3: {3,4,5}.
%C 0 has smallest string attractor size 1;
%C 01 has smallest string attractor size 2;
%C 001011 has smallest string attractor size 3;
%C 000100101011 has smallest string attractor size 4;
%C 0001001010110111 has smallest string attractor size 5.
%C These are the shortest binary strings achieving this minimum attractor size.
%H D. Kempa and N. Prezza. <a href="https://dl.acm.org/doi/abs/10.1145/3188745.3188814">At the roots of dictionary compression: string attractors</a>. In STOC'18 Proceedings, ACM Press, 2018, pp. 827-840.
%o (Python)
%o from itertools import product, combinations
%o def blocks_ranges(w):
%o blocks = dict()
%o for i in range(len(w)):
%o for j in range(i+1, len(w)+1):
%o wij = w[i:j]
%o if wij in blocks: blocks[wij].append(set(range(i, j)))
%o else: blocks[wij] = [set(range(i, j))]
%o return blocks
%o def is_attractor(S, w):
%o br = blocks_ranges(w)
%o for b in br:
%o for i in range(len(br[b])):
%o if S & br[b][i]: break
%o else: return False
%o return True
%o def lsa(w): # length of smallest attractor of w
%o for r in range(1, len(w)+1):
%o for s in combinations(range(len(w)), r):
%o if is_attractor(set(s), w): return r
%o def a(n): # only search strings starting with 0 by symmetry
%o return max(lsa("0"+"".join(u)) for u in product("01", repeat=n-1))
%o print([a(n) for n in range(1, 12)]) # _Michael S. Branicky_, Dec 20 2020
%K nonn,more
%O 1,2
%A _Jeffrey Shallit_, Dec 12 2020
%E (17)-a(19) from _Michael S. Branicky_, Dec 20 2020