login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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, 9056642, 19158430, 40409800, 85006554, 178392666, 373546760, 780628626, 1628332454, 3390841918, 7050048360, 14636882444, 30347358688, 62842024406 (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. 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 2 06:48 EST 2023. Contains 360000 sequences. (Running on oeis4.)