login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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 A204991 A054516

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 28 13:47 EST 2021. Contains 349413 sequences. (Running on oeis4.)