|
%I #61 Mar 19 2022 09:36:18
%S 2,6,18,48,124,302,720,1672,3828,8624,19222,42402,92824,201730,435848,
%T 936548,2003292,4267162,9056642,19158430,40409800,85006554,178392666,
%U 373546760,780628626,1628332454,3390841918,7050048360,14636882444,30347358688,62842024406
%N Sum of lengths of longest unbordered subword, over all binary words of length n.
%C By "subword" we mean a contiguous substring within a word. A string x is "bordered" if it has some nonempty prefix (other than x) that is also a suffix, and "unbordered" otherwise.
%D Pawel Gawrychowski, Gregory Kucherov, Benjamin Sach, and Tatiana Starikovskaya, "Computing the Longest Unbordered Substring", in C. Iliopoulos et al. (Eds.): SPIRE 2015, LNCS 9309, pp. 246-257, 2015.
%H Pawel Gawrychowski, Gregory Kucherov, Benjamin Sach, and Tatiana Starikovskaya, <a href="https://hal.archives-ouvertes.fr/hal-01250721">Computing the Longest Unbordered Substring</a>, in C. Iliopoulos et al. (Eds.): SPIRE 2015, LNCS 9309, 2015.
%e For n = 3 the longest unbordered subwords of 000,111 are of length 1; of 010,101 are of length 2; and for all others are of length 3. So a(3) = 1+1+2+2+3+3+3+3 = 18.
%o (Python)
%o from itertools import product
%o def bordered(b):
%o for i in range(len(b)-1, 0, -1):
%o if b[:i] == b[-i:]: return True
%o return False
%o def m(b):
%o for i in range(len(b), 0, -1):
%o for j in range(len(b)-i+1):
%o if not bordered(b[j:j+i]):
%o return i
%o return 0
%o def a(n): return 2*sum(m("0"+"".join(b)) for b in product("01", repeat=n-1))
%o print([a(n) for n in range(1, 19)]) # _Michael S. Branicky_, Mar 19 2022
%K nonn
%O 1,1
%A _Jeffrey Shallit_, Feb 17 2018
%E a(19) and beyond from _Michael S. Branicky_, Mar 19 2022
|
