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

0, 1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 15, 16, 17, 18, 19, 21, 23, 31, 32, 33, 34, 35, 36, 37, 39, 42, 43, 45, 47, 63, 64, 65, 66, 67, 68, 69, 71, 73, 74, 75, 77, 79, 85, 87, 91, 95, 127, 128, 129, 130, 131, 132, 133, 135, 136, 137, 138, 139, 141, 143, 146, 147

Offset: 1

Author

Gus Wiseman, Apr 25 2020

Keywords

• nonn

Comments

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.

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.

Examples

			The sequence of all reversed necklace co-necklaces begins:
    0: ()            31: (1,1,1,1,1)       69: (4,2,1)
    1: (1)           32: (6)               71: (4,1,1,1)
    2: (2)           33: (5,1)             73: (3,3,1)
    3: (1,1)         34: (4,2)             74: (3,2,2)
    4: (3)           35: (4,1,1)           75: (3,2,1,1)
    5: (2,1)         36: (3,3)             77: (3,1,2,1)
    7: (1,1,1)       37: (3,2,1)           79: (3,1,1,1,1)
    8: (4)           39: (3,1,1,1)         85: (2,2,2,1)
    9: (3,1)         42: (2,2,2)           87: (2,2,1,1,1)
   10: (2,2)         43: (2,2,1,1)         91: (2,1,2,1,1)
   11: (2,1,1)       45: (2,1,2,1)         95: (2,1,1,1,1,1)
   15: (1,1,1,1)     47: (2,1,1,1,1)      127: (1,1,1,1,1,1,1)
   16: (5)           63: (1,1,1,1,1,1)    128: (8)
   17: (4,1)         64: (7)              129: (7,1)
   18: (3,2)         65: (6,1)            130: (6,2)
   19: (3,1,1)       66: (5,2)            131: (6,1,1)
   21: (2,2,1)       67: (5,1,1)          132: (5,3)
   23: (2,1,1,1)     68: (4,3)            133: (5,2,1)
		

Crossrefs

The aperiodic case is A334266.

Compositions of this type are counted by A334271.

Normal sequences of this type are counted by A334272.

Another ranking of the same compositions is A334274 (binary expansion).

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

Necklace compositions are counted by A008965.

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

- Necklaces are A065609.

- Reversed necklaces are A333943.

- Co-necklaces are A333764.

- Reversed co-necklaces are A328595.

- Lyndon words are A275692.

- Co-Lyndon words are A326774.

- Reversed Lyndon words are A334265.

- Reversed co-Lyndon words are A328596.

- Aperiodic compositions are A328594.

Cf. A019536, A034691, A059966, A060223, A329138, A334269, A334270.

Programs

Mathematica

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
neckQ[q_]:=Length[q]==0||Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];
coneckQ[q_]:=Length[q]==0||Array[OrderedQ[{RotateRight[q,#],q}]&,Length[q]-1,1,And];
Select[Range[0,100],neckQ[Reverse[stc[#]]]&&coneckQ[stc[#]]&]