|
%I #22 Dec 21 2020 01:52:18
%S 1,2,2,6,4,20,12,66,46,20,12,4,72,48,36,24,8,4,44,16,374,202,146,76,
%T 36,20,8,4,242,132,72,28,688,440,292
%N Number of binary strings of length n that have the maximum number (A248958(n)) of distinct nonempty squares.
%C The values a(3) = 4 and a(12) = 36 reported in the linked paper are incorrect. Indeed, the strings of length 3 containing one square are 6: 000, 001, 011, 100, 110, and 111. - _Giovanni Resta_, Jul 29 2018
%C All terms after a(0) are even by symmetry. - _Michael S. Branicky_, Dec 20 2020
%H Aviezri S. Fraenkel and Jamie Simpson, <a href="http://dx.doi.org/10.1006/jcta.1997.2843">How Many Squares Can a String Contain?</a>, Journal of Combinatorial Theory, Series A 82, 112-120 (1998). See Table 1.
%t a[n_] := Sort[ Tally[ Length@ Union@ StringCases[ StringJoin @@ #, x__ ~~ x__, Overlaps -> All] & /@ Tuples[{"0", "1"}, n]]][[-1, 2]]; a /@ Range[0, 16] (* _Giovanni Resta_, Jul 29 2018 *)
%o (Python)
%o from itertools import product
%o from collections import Counter
%o def a(n): # except for 0, twice count of beginning with 0 by symmetry
%o if n == 0: return 1
%o squares = set("".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("01", repeat=n-1))
%o c = Counter(len(squares &
%o set(w[i:j] for i in range(n) for j in range(i+1, n+1))) for w in words)
%o return 2*c[max(c)]
%o print([a(n) for n in range(18)]) # _Michael S. Branicky_, Dec 20 2020 after _Giovanni Resta_
%Y Cf. A248958.
%K nonn,more
%O 0,2
%A _Michel Marcus_, Jul 26 2018
%E a(3) and a(12) corrected by and a(14)-a(34) from _Giovanni Resta_, Jul 29 2018
|
