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

2, 6, 18, 48, 124, 302, 720, 1672, 3828, 8624, 19222, 42402, 92824, 201730, 435848, 936548, 2003292, 4267162, 9056642, 19158430, 40409800, 85006554, 178392666, 373546760, 780628626, 1628332454, 3390841918, 7050048360, 14636882444, 30347358688, 62842024406

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. 246-257, 2015.

Links

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

Pawel Gawrychowski, Gregory Kucherov, Benjamin Sach, and Tatiana Starikovskaya, Computing the Longest Unbordered Substring, in C. Iliopoulos et al. (Eds.): SPIRE 2015, LNCS 9309, 2015.

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.

Prog

(Python)
from itertools import product
def bordered(b):
    for i in range(len(b)-1, 0, -1):
        if b[:i] == b[-i:]: return True
    return False
def m(b):
    for i in range(len(b), 0, -1):
        for j in range(len(b)-i+1):
            if not bordered(b[j:j+i]):
                return i
    return 0
def a(n): return 2*sum(m("0"+"".join(b)) for b in product("01", repeat=n-1))
print([a(n) for n in range(1, 19)]) # Michael S. Branicky, Mar 19 2022

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

Extensions

a(19) and beyond from Michael S. Branicky, Mar 19 2022

Status

approved