A317586 -id:A317586 - cp's OEIS frontend

A318687 Number of length-n circular binary words having exactly n distinct blocks of length floor(log_2(n)) + 1 (A070939).

2, 1, 2, 3, 2, 3, 4, 12, 14, 17, 14, 13, 12, 20, 32, 406, 538, 703, 842, 1085, 1310, 1465, 1544, 1570, 1968, 2132, 2000, 2480, 2176, 2816, 4096, 1060280

Offset: 1

Jeffrey Shallit, Aug 31 2018

A "circular word" (a.k.a. "necklace") is one that wraps around from the end to the beginning. The words are counted up to an equivalence where two circular words are the same if one is a cyclic shift of the other.

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.

Cf. A317586, which studies a similar quantity for two different lengths of blocks.

Cf. A070939.

a(2^n-1) = 2^(2^(n-1)-n+1) since A317586(2^n) = 2^(2^(n-1)-n) and A317586(2^n-1) = A317586(2^n+1) = 2*A317586(2^n) = 2^(2^(n-1)-n+1). - Altug Alkan, Sep 05 2018

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

Original entry on oeis.org

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

Jeffrey Shallit, Jul 21 2018

nonn

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.

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.

Cf. A317586.

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.

A330307 Number of circular ternary words of length n having the maximum possible number of distinct blocks of length floor(log_3 n) and floor(log_3 n)+1.

Original entry on oeis.org

3, 3, 2, 9, 18, 20, 24, 36, 24, 108, 468, 1554, 4308, 10128, 21144, 40080, 68496, 105840, 153120, 206976, 259648, 317952

Offset: 1

Jeffrey Shallit, Dec 10 2019

A circular word (a.k.a. "necklace") can be viewed as a representative of the equivalence class under cyclic shift.
The words counted by this sequence have 3^i distinct blocks of length i = floor(log_3 n) and n distinct blocks of length i+1.
This sequence counts a certain natural generalization of ternary de Bruijn words, which are cyclic words of length 3^n containing all n-length blocks as subwords.

			For n = 5 the 18 strings are those arising from applying all permutations of the alphabet to {00102, 00112, 00121, 00122, 01022, 01102, 01121, 01122, 01211, 01221} and selecting the lexicographically least representative up to shift.

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.

The ternary analog of A317586.

cp's OEIS Frontend

A318687 Number of length-n circular binary words having exactly n distinct blocks of length floor(log_2(n)) + 1 (A070939).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A330307 Number of circular ternary words of length n having the maximum possible number of distinct blocks of length floor(log_3 n) and floor(log_3 n)+1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs