login
Numbers k such that the k-th composition in standard order is both a necklace and a reversed co-necklace.
5

%I #7 Apr 28 2020 00:14:50

%S 0,1,2,3,4,6,7,8,10,12,14,15,16,20,24,26,28,30,31,32,36,40,42,48,52,

%T 54,56,58,60,62,63,64,72,80,84,96,100,104,106,108,112,116,118,120,122,

%U 124,126,127,128,136,144,160,164,168,170,192,200,204,208,212,216

%N Numbers k such that the k-th composition in standard order is both a necklace and a reversed co-necklace.

%C Also numbers whose binary expansion is both a reversed necklace and a co-necklace.

%C A necklace is a finite sequence of positive integers that is lexicographically less than or equal to any cyclic rotation. Co-necklaces are defined similarly, except with greater instead of less.

%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 co-necklace necklaces begins:

%e 0: () 31: (1,1,1,1,1) 100: (1,3,3)

%e 1: (1) 32: (6) 104: (1,2,4)

%e 2: (2) 36: (3,3) 106: (1,2,2,2)

%e 3: (1,1) 40: (2,4) 108: (1,2,1,3)

%e 4: (3) 42: (2,2,2) 112: (1,1,5)

%e 6: (1,2) 48: (1,5) 116: (1,1,2,3)

%e 7: (1,1,1) 52: (1,2,3) 118: (1,1,2,1,2)

%e 8: (4) 54: (1,2,1,2) 120: (1,1,1,4)

%e 10: (2,2) 56: (1,1,4) 122: (1,1,1,2,2)

%e 12: (1,3) 58: (1,1,2,2) 124: (1,1,1,1,3)

%e 14: (1,1,2) 60: (1,1,1,3) 126: (1,1,1,1,1,2)

%e 15: (1,1,1,1) 62: (1,1,1,1,2) 127: (1,1,1,1,1,1,1)

%e 16: (5) 63: (1,1,1,1,1,1) 128: (8)

%e 20: (2,3) 64: (7) 136: (4,4)

%e 24: (1,4) 72: (3,4) 144: (3,5)

%e 26: (1,2,2) 80: (2,5) 160: (2,6)

%e 28: (1,1,3) 84: (2,2,3) 164: (2,3,3)

%e 30: (1,1,1,2) 96: (1,6) 168: (2,2,4)

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

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

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

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

%Y The aperiodic case is A334267.

%Y Compositions of this type are counted by A334271.

%Y Normal sequences of this type are counted by A334272.

%Y Binary (or reversed binary) necklaces are counted by A000031.

%Y Necklace compositions are counted by A008965.

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

%Y - Necklaces are A065609.

%Y - Reversed necklaces are A333943.

%Y - Co-necklaces are A333764.

%Y - Reversed co-necklaces are A328595.

%Y - Lyndon words are A275692.

%Y - Co-Lyndon words are A326774.

%Y - Reversed Lyndon words are A334265.

%Y - Reversed co-Lyndon words are A328596.

%Y - Aperiodic compositions are A328594.

%Y Cf. A019536, A034691, A059966, A060223, A329138, A334266, A334269, A334270.

%K nonn

%O 1,3

%A _Gus Wiseman_, Apr 25 2020