OFFSET
1,1
COMMENTS
Two strings are conjugate if one is a cyclic shift of the other, such as "listen" and "enlist".
If w is a string, then C(w) is the set of all conjugates of w. Thus C(001) = {001, 100, 010}.
The state complexity of a finite set of strings S is the size (i.e., the number of states) of the smallest (complete) deterministic finite automaton (DFA) recognizing S.
LINKS
D. Gabric, S. Holub, and J. Shallit, Generalized de Bruijn words and the state complexity of conjugate sets, arXiv:1903.05442 [cs.FL], March 13 2019.
FORMULA
a(n) = n^2 - (2i-3)2^i - j(2i+1) - 1 = 2^{2i} + (2j-2i+3)2^i + j^2 - (2i+1)j - 1, if n = 2^i + j with 0 <= j < 2^i.
CROSSREFS
KEYWORD
nonn
AUTHOR
Jeffrey Shallit, Jul 21 2018
STATUS
approved