A331392 Sum, over all binary strings w of length n, of the length of the shortest border of w.

0, 2, 4, 12, 24, 60, 120, 264, 528, 1116, 2232, 4584, 9168, 18616, 37232, 75056, 150112, 301556, 603112, 1209064, 2418128, 4842504, 9685008, 19383408, 38766816, 77562648, 155125296, 310312528, 620625056, 1241382832, 2482765664, 4965813280, 9931626560

Offset

1,2

Comments

A nonempty word w is a border of a string x if w is both a prefix and suffix of x, and w does not equal x.

Links

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

Formula

From Rémy Sigrist, Jan 16 2020: (Start)

Apparently, for any k > 0:

- a(2*k+1) = 2*a(k),

- a(2*k) = 2*a(2*k-1) + 2*k*A045690(k).

(End)

Example

For n = 3, the words are 000,001,010,011 and their binary complements.  The shortest border of 000 and 010 is 0, and the other words have no border.  So a(3) = 4.

Crossrefs

Cf. A045690, A091065, A331393.

Sequence in context: A233411 A057422 A036045 * A100538 A303794 A135139

Adjacent sequences: A331389 A331390 A331391 * A331393 A331394 A331395

Keyword

nonn

Author

Jeffrey Shallit, Jan 15 2020

Extensions

More terms from Rémy Sigrist, Jan 15 2020

Status

approved