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

%I #32 Dec 20 2020 11:04:02

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

%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