A334811 Length of shortest overlap-free binary word having n periods.

1, 2, 5, 12, 46, 182, 726

Offset

1,2

Comments

A word is "overlap-free" if it contains no block of the form axaxa, where a is a single letter and x is a (possibly empty) block. The "period" of a word w is an integer p, 1 <= p <= |w|, such that w[i] = w[i+p] for all indices i that make sense. A nonempty word w trivially has period |w|.

Links

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

Daniel Gabric, Narad Rampersad, and Jeffrey Shallit, An inequality for the number of periods in a word, arXiv:2005.11718 [cs.DM], 2020.

Formula

Conjecture: a(n) = (17/6)*4^(n-3) + 2/3 for n >= 4.

Example

Here are the lexicographically least examples for 1 <= n <= 6:
1: 0
2: 00
3: 00100
4: 001001100100
5: 0011001011010011001011001101001100101101001100
6: 0011001011001101001100101101001011001101001011010011001011001\
   1010011001011010010110011010011001011001101001011010011001011\
   001101001100101101001011001101001011010011001011001101001100

Crossrefs

Cf. A332866.

Sequence in context: A127137 A172239 A183758 * A071787 A343813 A332791

Adjacent sequences: A334808 A334809 A334810 * A334812 A334813 A334814

Keyword

nonn,more,hard

Author

Jeffrey Shallit, May 12 2020

Status

approved