|
|
A248958
|
|
Maximum number of distinct nonempty squares in a binary string of length n.
|
|
2
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|