

A295499


Sum of lengths of longest unbordered subword, over all binary words of length n.


0



2, 6, 18, 48, 124, 302, 720, 1672, 3828, 8624, 19222, 42402, 92824, 201730, 435848, 936548, 2003292, 4267162
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

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.


REFERENCES

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. 246257, 2015.


LINKS

Table of n, a(n) for n=1..18.


EXAMPLE

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.


CROSSREFS

Sequence in context: A217526 A018027 A218759 * A059413 A256828 A197055
Adjacent sequences: A295496 A295497 A295498 * A295500 A295501 A295502


KEYWORD

nonn


AUTHOR

Jeffrey Shallit, Feb 17 2018


STATUS

approved



