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