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
KEYWORD
nonn,more,hard
AUTHOR
Jeffrey Shallit, May 12 2020
STATUS
approved