|
|
A329312
|
|
Length of the co-Lyndon factorization of the binary expansion of n.
|
|
43
|
|
|
1, 1, 2, 1, 2, 1, 3, 1, 2, 2, 3, 1, 2, 1, 4, 1, 2, 2, 3, 1, 3, 2, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 2, 3, 2, 3, 2, 4, 1, 2, 3, 4, 2, 3, 2, 5, 1, 2, 1, 3, 1, 2, 2, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 2, 3, 2, 3, 2, 4, 1, 3, 3, 4, 2, 3, 2, 5, 1, 2, 2, 3, 1, 4, 3
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
The co-Lyndon product of two or more finite sequences is defined to be the lexicographically minimal sequence obtainable by shuffling the sequences together. For example, the co-Lyndon product of (231) and (213) is (212313), the product of (221) and (213) is (212213), and the product of (122) and (2121) is (1212122). A co-Lyndon word is a finite sequence that is prime with respect to the co-Lyndon product. Equivalently, a co-Lyndon word is a finite sequence that is lexicographically strictly greater than all of its cyclic rotations. Every finite sequence has a unique (orderless) factorization into co-Lyndon words, and if these factors are arranged in a certain order, their concatenation is equal to their co-Lyndon product. For example, (1001) has sorted co-Lyndon factorization (1)(100).
Also the length of the Lyndon factorization of the inverted binary expansion of n, where the inverted digits are 1 minus the binary digits.
|
|
LINKS
|
|
|
EXAMPLE
|
The binary indices of 1..20 together with their co-Lyndon factorizations are:
1: (1) = (1)
2: (10) = (10)
3: (11) = (1)(1)
4: (100) = (100)
5: (101) = (10)(1)
6: (110) = (110)
7: (111) = (1)(1)(1)
8: (1000) = (1000)
9: (1001) = (100)(1)
10: (1010) = (10)(10)
11: (1011) = (10)(1)(1)
12: (1100) = (1100)
13: (1101) = (110)(1)
14: (1110) = (1110)
15: (1111) = (1)(1)(1)(1)
16: (10000) = (10000)
17: (10001) = (1000)(1)
18: (10010) = (100)(10)
19: (10011) = (100)(1)(1)
20: (10100) = (10100)
|
|
MATHEMATICA
|
colynQ[q_]:=Array[Union[{RotateRight[q, #], q}]=={RotateRight[q, #], q}&, Length[q]-1, 1, And];
colynfac[q_]:=If[Length[q]==0, {}, Function[i, Prepend[colynfac[Drop[q, i]], Take[q, i]]]@Last[Select[Range[Length[q]], colynQ[Take[q, #]]&]]];
Table[Length[colynfac[IntegerDigits[n, 2]]], {n, 100}]
|
|
CROSSREFS
|
Cf. A000031, A001037, A059966, A060223, A211097, A296372, A296658, A329131, A329314, A329318, A329324, A329325.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|