A331699 Sum of ceiling(n/per(w)) over all binary words of length n.

2, 6, 14, 30, 60, 118, 236, 460, 914, 1810, 3608, 7158, 14310, 28504, 56978, 113778, 227484, 454534, 909050, 1817232, 3634344, 7267198, 14534120, 29064982, 58129922, 116253394, 232506236, 465000468, 929999880, 1859974762, 3719949488, 7439848936, 14879695742

Offset

1,1

Comments

The period per(w), for w = w[1..n] a word, is the least p >= 1 such that w[i] = w[i+p] for 1 <= i <= n-p.

Asymptotically we have a(n) ~ 1.732213...*2^n.

Links

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

D. Gabric and J. Shallit, Avoidance of split overlaps, arxiv preprint arXiv:2002.01968 [cs.DM], February 5 2020.

Rémy Sigrist, C program for A331699, Jan 26 2020.

Example

For n = 3 there are two words of period 1 (000 and 111), two words of period 2 (010 and 101), and all other words are of period 3.  So a(n) = 2*ceiling(3/1) + 2*ceiling(3/2) + 4*ceiling(3/3) = 14.

Prog

(C) See Links section.

Crossrefs

Sequence in context: A192966 A339668 A260058 * A327048 A228038 A122958

Adjacent sequences: A331696 A331697 A331698 * A331700 A331701 A331702

Keyword

nonn

Author

Jeffrey Shallit, Jan 25 2020

Extensions

a(25)-a(33) from Rémy Sigrist, Jan 26 2020

Status

approved