A317368 Number of binary strings of length n that have the maximum number (A248958(n)) of distinct nonempty squares.

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

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

All terms after a(0) are even by symmetry. - Michael S. Branicky, Dec 20 2020

Links

Table of n, a(n) for n=0..34.

Aviezri S. Fraenkel and Jamie Simpson, How Many Squares Can a String Contain?, Journal of Combinatorial Theory, Series A 82, 112-120 (1998). See Table 1.

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)]
print([a(n) for n in range(18)]) # Michael S. Branicky, Dec 20 2020 after Giovanni Resta

Crossrefs

Cf. A248958.

Sequence in context: A061807 A062885 A062293 * A259882 A356187 A204991

Adjacent sequences: A317365 A317366 A317367 * A317369 A317370 A317371

Keyword

nonn,more

Author

Michel Marcus, Jul 26 2018

Extensions

a(3) and a(12) corrected by and a(14)-a(34) from Giovanni Resta, Jul 29 2018

Status

approved