A329399 Numbers whose reversed binary expansion has uniform Lyndon factorization.

1, 2, 3, 4, 6, 7, 8, 10, 12, 14, 15, 16, 20, 24, 26, 28, 30, 31, 32, 36, 38, 40, 42, 44, 48, 52, 54, 56, 58, 60, 62, 63, 64, 72, 80, 84, 88, 92, 96, 100, 104, 106, 108, 112, 116, 118, 120, 122, 124, 126, 127, 128, 136, 140, 142, 144, 152, 160, 164, 168, 170

Offset: 1

Author

Gus Wiseman, Nov 13 2019

Keywords

• nonn

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).

A sequence of words is uniform if they all have the same length.

Examples

			The sequence of terms together with their reversed binary expansions and Lyndon factorizations begins:
   1:      (1) = (1)
   2:     (01) = (01)
   3:     (11) = (1)(1)
   4:    (001) = (001)
   6:    (011) = (011)
   7:    (111) = (1)(1)(1)
   8:   (0001) = (0001)
  10:   (0101) = (01)(01)
  12:   (0011) = (0011)
  14:   (0111) = (0111)
  15:   (1111) = (1)(1)(1)(1)
  16:  (00001) = (00001)
  20:  (00101) = (00101)
  24:  (00011) = (00011)
  26:  (01011) = (01011)
  28:  (00111) = (00111)
  30:  (01111) = (01111)
  31:  (11111) = (1)(1)(1)(1)(1)
  32: (000001) = (000001)
  36: (001001) = (001)(001)
  38: (011001) = (011)(001)
  40: (000101) = (000101)
  42: (010101) = (01)(01)(01)
  44: (001101) = (001101)
  48: (000011) = (000011)
		

Crossrefs

Numbers whose binary expansion has uniform Lyndon factorization and uniform co-Lyndon factorization are A023758.

Numbers whose reversed binary expansion is Lyndon are A328596.

Numbers whose binary expansion is co-Lyndon are A275692.

Numbers whose trimmed binary expansion has Lyndon and co-Lyndon factorizations of equal lengths are A329395.

Cf. A001037, A059966, A060223, A102659, A211100, A329131, A329312, A329313, A329318, A329326, A329396.

Programs

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,#]]&]]]];
Select[Range[100],SameQ@@Length/@lynfac[Reverse[IntegerDigits[#,2]]]&]