A248958 Maximum number of distinct nonempty squares in a binary string of length n.

0, 1, 1, 2, 2, 3, 3, 4, 5, 6, 7, 7, 8, 9, 10, 11, 12, 12, 13, 13, 14, 15, 16, 17, 18, 19, 20, 20, 21, 22, 23, 23, 24, 25

Offset

1,4

Comments

If w is a string and there exist strings, x,u,y such that w = xuuy then uu is a square in w.

Fraenkel and Simpson also give a(20)=13 and a(22)=15. - Michel Marcus, Jul 26 2018

Links

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

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

Giovanni Resta, Examples of strings which contain a(n) squares for n=1..34

Example

a(7) = 3. The string 1101101 contains three distinct squares 11, 110110 and 101101. All other strings of length 7 have 3 or fewer distinct squares.

Mathematica

a[n_] := Max[Length@ Union@ StringCases[ StringJoin @@ #, x__ ~~ x__, Overlaps -> All] & /@ Tuples[{"0", "1"}, n]]; Array[a, 16] (* Giovanni Resta, Jul 29 2018 *)

Prog

(Python)
from itertools import product
def a(n): # only check strings starting with 0 by symmetry
  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))
  return max(len(squares &
    set(w[i:j] for i in range(n) for j in range(i+1, n+1))) for w in words)
print([a(n) for n in range(1, 18)]) # Michael S. Branicky, Dec 20 2020 after Giovanni Resta

Crossrefs

Cf. A105098, A317368.

Sequence in context: A117144 A104408 A008718 * A030719 A126027 A111581

Adjacent sequences: A248955 A248956 A248957 * A248959 A248960 A248961

Keyword

nonn,more

Author

W. Edwin Clark, Oct 17 2014

Extensions

Corrected and extended by Jeffrey Shallit, Mar 24 2017

a(19)-a(34) from Giovanni Resta, Jul 29 2018

Status

approved