login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A331392 Sum, over all binary strings w of length n, of the length of the shortest border of w. 1
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 (list; graph; refs; listen; history; text; internal format)
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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 31 22:45 EDT 2020. Contains 334756 sequences. (Running on oeis4.)