A277133 Number of distinct sets of periods of length >= ceiling(n/2) in all binary strings of length n.

1, 2, 2, 4, 4, 7, 7, 11, 11, 17, 17, 25, 25, 35, 35, 48, 48, 65, 65, 86, 86, 113, 113, 143, 143, 180, 180, 227, 227, 284, 284, 346, 346, 421, 421, 508, 508, 610, 610, 726, 726, 861

Offset

1,2

Comments

A period of a string x of length n is an integer p such that x[i] = x[i+p] for 1 <= i <= n-p.

From Jeffrey Shallit, Jan 17 2019: (Start)

Alternatively, the number of distinct sets of border lengths, restricted to at most n/2 in length, possible over all binary strings of length n. A border of a word is a nonempty prefix that is also a suffix.

Alternatively, the number of distinct sets of lengths of palindromes that can begin a binary word of length n. (End)

Links

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

Example

For n = 5, the possible sets of periods of length >=3 are {5}, {3,5}, {4,5}, {3,4,5}, achieved by the strings 00001, 01001, 00010, 00100, respectively.

Crossrefs

Cf. A005434, which is the sequence where there is no restriction on the size of the periods.

Sequence in context: A099770 A099383 A341972 * A323539 A280954 A339244

Adjacent sequences: A277130 A277131 A277132 * A277134 A277135 A277136

Keyword

nonn,more

Author

Jeffrey Shallit, Oct 01 2016

Extensions

a(21)-a(42) from Lars Blomberg, Oct 08 2016

Status

approved