login
A316936
a(n) is the maximum state complexity of the language C(w) of conjugates of w, over all length-n binary strings w.
0
3, 5, 7, 11, 15, 21, 29, 39, 49, 61, 75, 91, 109, 129, 151, 175, 199, 225, 253, 283, 315, 349, 385, 423, 463, 505, 549, 595, 643, 693, 745, 799, 853, 909, 967, 1027, 1089, 1153, 1219, 1287, 1357, 1429, 1503, 1579, 1657, 1737, 1819, 1903, 1989, 2077, 2167, 2259
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
Cf. A317586.
Sequence in context: A252793 A351924 A062488 * A116582 A052003 A019449
KEYWORD
nonn
AUTHOR
Jeffrey Shallit, Jul 21 2018
STATUS
approved