OFFSET
1,3
COMMENTS
Reversed Lyndon words are different from co-Lyndon words (A326774).
A Lyndon word is a finite sequence of positive integers that is lexicographically strictly less than all of its cyclic rotations.
The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.
EXAMPLE
The sequence of all reversed Lyndon words begins:
0: () 37: (3,2,1) 83: (2,3,1,1)
1: (1) 39: (3,1,1,1) 85: (2,2,2,1)
2: (2) 41: (2,3,1) 87: (2,2,1,1,1)
4: (3) 43: (2,2,1,1) 91: (2,1,2,1,1)
5: (2,1) 47: (2,1,1,1,1) 95: (2,1,1,1,1,1)
8: (4) 64: (7) 128: (8)
9: (3,1) 65: (6,1) 129: (7,1)
11: (2,1,1) 66: (5,2) 130: (6,2)
16: (5) 67: (5,1,1) 131: (6,1,1)
17: (4,1) 68: (4,3) 132: (5,3)
18: (3,2) 69: (4,2,1) 133: (5,2,1)
19: (3,1,1) 71: (4,1,1,1) 135: (5,1,1,1)
21: (2,2,1) 73: (3,3,1) 137: (4,3,1)
23: (2,1,1,1) 74: (3,2,2) 138: (4,2,2)
32: (6) 75: (3,2,1,1) 139: (4,2,1,1)
33: (5,1) 77: (3,1,2,1) 141: (4,1,2,1)
34: (4,2) 79: (3,1,1,1,1) 143: (4,1,1,1,1)
35: (4,1,1) 81: (2,4,1) 145: (3,4,1)
MATHEMATICA
stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n, 2]], 1], 0]]//Reverse;
lynQ[q_]:=Length[q]==0||Array[Union[{q, RotateRight[q, #1]}]=={q, RotateRight[q, #1]}&, Length[q]-1, 1, And];
Select[Range[0, 100], lynQ[Reverse[stc[#]]]&]
CROSSREFS
The non-reversed version is A275692.
The generalization to necklaces is A333943.
The dual version (reversed co-Lyndon words) is A328596.
The case that is also co-Lyndon is A334266.
Binary Lyndon words are counted by A001037.
Lyndon compositions are counted by A059966.
Normal Lyndon words are counted by A060223.
Numbers whose prime signature is a reversed Lyndon word are A334298.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Necklaces are A065609.
- Sum is A070939.
- Reverse is A228351 (triangle).
- Strict compositions are A233564.
- Constant compositions are A272919.
- Lyndon words are A275692.
- Reversed Lyndon words are A334265 (this sequence).
- Co-Lyndon words are A326774.
- Reversed co-Lyndon words are A328596.
- Length of Lyndon factorization is A329312.
- Distinct rotations are counted by A333632.
- Lyndon factorizations are counted by A333940.
- Length of Lyndon factorization of reverse is A334297.
KEYWORD
nonn
AUTHOR
Gus Wiseman, Apr 22 2020
STATUS
approved