|
|
A317368
|
|
Number of binary strings of length n that have the maximum number (A248958(n)) of distinct nonempty squares.
|
|
1
|
|
|
1, 2, 2, 6, 4, 20, 12, 66, 46, 20, 12, 4, 72, 48, 36, 24, 8, 4, 44, 16, 374, 202, 146, 76, 36, 20, 8, 4, 242, 132, 72, 28, 688, 440, 292
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
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
|
|
LINKS
|
|
|
MATHEMATICA
|
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 *)
|
|
PROG
|
(Python)
from itertools import product
from collections import Counter
def a(n): # except for 0, twice count of beginning with 0 by symmetry
if n == 0: return 1
squares = set("".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("01", repeat=n-1))
c = Counter(len(squares &
set(w[i:j] for i in range(n) for j in range(i+1, n+1))) for w in words)
return 2*c[max(c)]
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
a(3) and a(12) corrected by and a(14)-a(34) from Giovanni Resta, Jul 29 2018
|
|
STATUS
|
approved
|
|
|
|