login
Numbers k such that the k-th composition in standard order is a reversed Lyndon word.
10

%I #13 Apr 25 2020 08:40:24

%S 0,1,2,4,5,8,9,11,16,17,18,19,21,23,32,33,34,35,37,39,41,43,47,64,65,

%T 66,67,68,69,71,73,74,75,77,79,81,83,85,87,91,95,128,129,130,131,132,

%U 133,135,137,138,139,141,143,145,146,147,149,151,155,159,161,163

%N Numbers k such that the k-th composition in standard order is a reversed Lyndon word.

%C Reversed Lyndon words are different from co-Lyndon words (A326774).

%C A Lyndon word is a finite sequence of positive integers that is lexicographically strictly less than all of its cyclic rotations.

%C 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.

%e The sequence of all reversed Lyndon words begins:

%e 0: () 37: (3,2,1) 83: (2,3,1,1)

%e 1: (1) 39: (3,1,1,1) 85: (2,2,2,1)

%e 2: (2) 41: (2,3,1) 87: (2,2,1,1,1)

%e 4: (3) 43: (2,2,1,1) 91: (2,1,2,1,1)

%e 5: (2,1) 47: (2,1,1,1,1) 95: (2,1,1,1,1,1)

%e 8: (4) 64: (7) 128: (8)

%e 9: (3,1) 65: (6,1) 129: (7,1)

%e 11: (2,1,1) 66: (5,2) 130: (6,2)

%e 16: (5) 67: (5,1,1) 131: (6,1,1)

%e 17: (4,1) 68: (4,3) 132: (5,3)

%e 18: (3,2) 69: (4,2,1) 133: (5,2,1)

%e 19: (3,1,1) 71: (4,1,1,1) 135: (5,1,1,1)

%e 21: (2,2,1) 73: (3,3,1) 137: (4,3,1)

%e 23: (2,1,1,1) 74: (3,2,2) 138: (4,2,2)

%e 32: (6) 75: (3,2,1,1) 139: (4,2,1,1)

%e 33: (5,1) 77: (3,1,2,1) 141: (4,1,2,1)

%e 34: (4,2) 79: (3,1,1,1,1) 143: (4,1,1,1,1)

%e 35: (4,1,1) 81: (2,4,1) 145: (3,4,1)

%t stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;

%t lynQ[q_]:=Length[q]==0||Array[Union[{q,RotateRight[q,#1]}]=={q,RotateRight[q,#1]}&,Length[q]-1,1,And];

%t Select[Range[0,100],lynQ[Reverse[stc[#]]]&]

%Y The non-reversed version is A275692.

%Y The generalization to necklaces is A333943.

%Y The dual version (reversed co-Lyndon words) is A328596.

%Y The case that is also co-Lyndon is A334266.

%Y Binary Lyndon words are counted by A001037.

%Y Lyndon compositions are counted by A059966.

%Y Normal Lyndon words are counted by A060223.

%Y Numbers whose prime signature is a reversed Lyndon word are A334298.

%Y All of the following pertain to compositions in standard order (A066099):

%Y - Length is A000120.

%Y - Necklaces are A065609.

%Y - Sum is A070939.

%Y - Reverse is A228351 (triangle).

%Y - Strict compositions are A233564.

%Y - Constant compositions are A272919.

%Y - Lyndon words are A275692.

%Y - Reversed Lyndon words are A334265 (this sequence).

%Y - Co-Lyndon words are A326774.

%Y - Reversed co-Lyndon words are A328596.

%Y - Length of Lyndon factorization is A329312.

%Y - Distinct rotations are counted by A333632.

%Y - Lyndon factorizations are counted by A333940.

%Y - Length of Lyndon factorization of reverse is A334297.

%Y Cf. A000031, A027375, A138904, A211100, A328595, A329131, A329313, A333764, A334028, A334267.

%K nonn

%O 1,3

%A _Gus Wiseman_, Apr 22 2020