login
A329400
Length of the co-Lyndon factorization of the binary expansion of n with the most significant (first) digit removed.
4
0, 1, 1, 2, 2, 1, 2, 3, 3, 2, 3, 1, 2, 1, 3, 4, 4, 3, 4, 2, 3, 2, 4, 1, 2, 2, 3, 1, 2, 1, 4, 5, 5, 4, 5, 3, 4, 3, 5, 2, 3, 3, 4, 2, 3, 2, 5, 1, 2, 2, 3, 1, 3, 2, 4, 1, 2, 1, 3, 1, 2, 1, 5, 6, 6, 5, 6, 4, 5, 4, 6, 3, 4, 4, 5, 3, 4, 3, 6, 2, 3, 3, 4, 2, 4, 3, 5
OFFSET
1,4
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).
EXAMPLE
Decapitated binary expansions of 1..20 together with their co-Lyndon factorizations:
1: () =
2: (0) = (0)
3: (1) = (1)
4: (00) = (0)(0)
5: (01) = (0)(1)
6: (10) = (10)
7: (11) = (1)(1)
8: (000) = (0)(0)(0)
9: (001) = (0)(0)(1)
10: (010) = (0)(10)
11: (011) = (0)(1)(1)
12: (100) = (100)
13: (101) = (10)(1)
14: (110) = (110)
15: (111) = (1)(1)(1)
16: (0000) = (0)(0)(0)(0)
17: (0001) = (0)(0)(0)(1)
18: (0010) = (0)(0)(10)
19: (0011) = (0)(0)(1)(1)
20: (0100) = (0)(100)
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[If[n==0, 0, Length[colynfac[Rest[IntegerDigits[n, 2]]]]], {n, 30}]
CROSSREFS
The non-"co" version is A211097.
The version involving all digits is A329312.
Lyndon and co-Lyndon compositions are (both) counted by A059966.
Numbers whose reversed binary expansion is Lyndon are A328596.
Numbers whose binary expansion is co-Lyndon are A275692.
Numbers whose decapitated binary expansion is co-Lyndon are A329401.
Sequence in context: A256478 A356245 A106638 * A131909 A307319 A131730
KEYWORD
nonn
AUTHOR
Gus Wiseman, Nov 16 2019
STATUS
approved