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,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

Table of n, a(n) for n=1..52.

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

Adjacent sequences: A316933 A316934 A316935 * A316937 A316938 A316939

Keyword

nonn

Author

Jeffrey Shallit, Jul 21 2018

Status

approved