A248958 - OEIS

%I #39 Dec 17 2024 10:14:08

%S 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,

%T 20,21,22,23,23,24,25

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

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

%C Fraenkel and Simpson also give a(20) = 13 and a(22) = 15. - _Michel Marcus_, Jul 26 2018

%H Srečko Brlek and Shuo Li, <a href="https://arxiv.org/abs/2204.10204">On the number of squares in a finite word</a>, arXiv:2204.10204 [math.CO], April 25 2022.

%H Aviezri S. Fraenkel and Jamie Simpson, <a href="http://dx.doi.org/10.1006/jcta.1997.2843">How Many Squares Can a String Contain?</a>, Journal of Combinatorial Theory, Series A 82, 112-120 (1998).

%H Giovanni Resta, <a href="/A248958/a248958.txt">Examples of strings which contain a(n) squares for n=1..34</a>

%F a(n) < n (proved by Brlek and Li, answering a longstanding conjecture). - _Jeffrey Shallit_, Dec 17 2024

%e 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.

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

%o (Python)

%o from itertools import product

%o def a(n): # only check strings starting with 0 by symmetry

%o   squares = set("".join(u) + "".join(u)

%o     for r in range(1, n//2 + 1) for u in product("01", repeat = r))

%o   words = ("0"+"".join(w) for w in product("01", repeat=n-1))

%o   return max(len(squares &

%o     set(w[i:j] for i in range(n) for j in range(i+1, n+1))) for w in words)

%o print([a(n) for n in range(1, 18)]) # _Michael S. Branicky_, Dec 20 2020 after _Giovanni Resta_

%Y Cf. A105098, A317368.

%K nonn,more

%O 1,4

%A _W. Edwin Clark_, Oct 17 2014

%E Corrected and extended by _Jeffrey Shallit_, Mar 24 2017

%E a(19)-a(34) from _Giovanni Resta_, Jul 29 2018