login
A334811
Length of shortest overlap-free binary word having n periods.
0
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
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
KEYWORD
nonn,more,hard
AUTHOR
Jeffrey Shallit, May 12 2020
STATUS
approved