login
A329395
Numbers whose binary expansion without the most significant (first) digit has Lyndon and co-Lyndon factorizations of equal lengths.
17
1, 2, 3, 4, 7, 8, 10, 13, 15, 16, 22, 25, 31, 32, 36, 42, 46, 49, 53, 59, 63, 64, 76, 82, 94, 97, 109, 115, 127, 128, 136, 148, 156, 162, 166, 169, 170, 172, 181, 182, 190, 193, 201, 202, 211, 213, 214, 217, 221, 227, 235, 247, 255, 256, 280, 292, 306, 308
OFFSET
1,2
COMMENTS
We define the Lyndon product of two or more finite sequences to be the lexicographically maximal sequence obtainable by shuffling the sequences together. For example, the Lyndon product of (231) with (213) is (232131), the product of (221) with (213) is (222131), and the product of (122) with (2121) is (2122121). A Lyndon word is a finite sequence that is prime with respect to the Lyndon product. Equivalently, a Lyndon word is a finite sequence that is lexicographically strictly less than all of its cyclic rotations. Every finite sequence has a unique (orderless) factorization into Lyndon words, and if these factors are arranged in lexicographically decreasing order, their concatenation is equal to their Lyndon product. For example, (1001) has sorted Lyndon factorization (001)(1).
Similarly, the co-Lyndon product is the lexicographically minimal sequence obtainable by shuffling the sequences together, and a co-Lyndon word is a finite sequence that is prime with respect to the co-Lyndon product, or, equivalently, a finite sequence that is lexicographically strictly greater than all of its cyclic rotations. For example, (1001) has sorted co-Lyndon factorization (1)(100).
Conjecture: also numbers k such that the k-th composition in standard order (A066099) is a palindrome, cf. A025065, A242414, A317085, A317086, A317087, A335373. - Gus Wiseman, Jun 06 2020
EXAMPLE
The sequence of terms together with their trimmed binary expansions and their co-Lyndon and Lyndon factorizations begins:
1: () = 0 = 0
2: (0) = (0) = (0)
3: (1) = (1) = (1)
4: (00) = (0)(0) = (0)(0)
7: (11) = (1)(1) = (1)(1)
8: (000) = (0)(0)(0) = (0)(0)(0)
10: (010) = (0)(10) = (01)(0)
13: (101) = (10)(1) = (1)(01)
15: (111) = (1)(1)(1) = (1)(1)(1)
16: (0000) = (0)(0)(0)(0) = (0)(0)(0)(0)
22: (0110) = (0)(110) = (011)(0)
25: (1001) = (100)(1) = (1)(001)
31: (1111) = (1)(1)(1)(1) = (1)(1)(1)(1)
32: (00000) = (0)(0)(0)(0)(0) = (0)(0)(0)(0)(0)
36: (00100) = (0)(0)(100) = (001)(0)(0)
42: (01010) = (0)(10)(10) = (01)(01)(0)
46: (01110) = (0)(1110) = (0111)(0)
49: (10001) = (1000)(1) = (1)(0001)
53: (10101) = (10)(10)(1) = (1)(01)(01)
59: (11011) = (110)(1)(1) = (1)(1)(011)
63: (11111) = (1)(1)(1)(1)(1) = (1)(1)(1)(1)(1)
MATHEMATICA
lynQ[q_]:=Array[Union[{q, RotateRight[q, #]}]=={q, RotateRight[q, #]}&, Length[q]-1, 1, And];
lynfac[q_]:=If[Length[q]==0, {}, Function[i, Prepend[lynfac[Drop[q, i]], Take[q, i]]][Last[Select[Range[Length[q]], lynQ[Take[q, #]]&]]]];
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, #]]&]]];
Select[Range[100], Length[lynfac[Rest[IntegerDigits[#, 2]]]]==Length[colynfac[Rest[IntegerDigits[#, 2]]]]&]
CROSSREFS
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.
Sequence in context: A220969 A207006 A171781 * A065294 A240073 A332579
KEYWORD
nonn
AUTHOR
Gus Wiseman, Nov 13 2019
STATUS
approved