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: A018027 A218759 A381208 * A059413 A377118 A256828

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