login
A331699
Sum of ceiling(n/per(w)) over all binary words of length n.
4
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
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
KEYWORD
nonn
AUTHOR
Jeffrey Shallit, Jan 25 2020
EXTENSIONS
a(25)-a(33) from Rémy Sigrist, Jan 26 2020
STATUS
approved