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
Srečko Brlek and Shuo Li, On the number of squares in a finite word, arXiv:2204.10204 [math.CO], April 25 2022.
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
FORMULA
a(n) < n (proved by Brlek and Li, answering a longstanding conjecture). - Jeffrey Shallit, Dec 17 2024
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
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