A316936 a(n) is the maximum state complexity of the language C(w) of conjugates of w, over all length-n binary strings w.

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

Author

Jeffrey Shallit, Jul 21 2018

Keywords

• nonn

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.

Crossrefs

Cf. A317586.

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.