A329358 Numbers whose binary expansion has Lyndon and co-Lyndon factorizations of equal lengths.

1, 3, 5, 7, 9, 15, 17, 21, 27, 31, 33, 45, 51, 63, 65, 73, 74, 83, 85, 86, 89, 93, 99, 107, 119, 127, 129, 138, 150, 153, 163, 165, 174, 177, 185, 189, 195, 203, 205, 219, 231, 255, 257, 266, 273, 274, 278, 291, 294, 297, 302, 305, 310, 313, 323, 325, 333, 341

Offset: 1

Author

Gus Wiseman, Nov 15 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).

Similarly, the co-Lyndon product is the lexicographically minimal sequence obtainable by shuffling the sequences together, and a co-Lyndon word is a finite sequence that is prime with respect to the co-Lyndon product, or, equivalently, a finite sequence that is lexicographically strictly greater than all of its cyclic rotations. For example, (1001) has sorted co-Lyndon factorization (1)(100).

Examples

			The binary expansions of the initial terms together with their Lyndon and co-Lyndon factorizations:
   1:       (1) =                (1) = (1)
   3:      (11) =             (1)(1) = (1)(1)
   5:     (101) =            (1)(01) = (10)(1)
   7:     (111) =          (1)(1)(1) = (1)(1)(1)
   9:    (1001) =           (1)(001) = (100)(1)
  15:    (1111) =       (1)(1)(1)(1) = (1)(1)(1)(1)
  17:   (10001) =          (1)(0001) = (1000)(1)
  21:   (10101) =        (1)(01)(01) = (10)(10)(1)
  27:   (11011) =        (1)(1)(011) = (110)(1)(1)
  31:   (11111) =    (1)(1)(1)(1)(1) = (1)(1)(1)(1)(1)
  33:  (100001) =         (1)(00001) = (10000)(1)
  45:  (101101) =       (1)(011)(01) = (10)(110)(1)
  51:  (110011) =       (1)(1)(0011) = (1100)(1)(1)
  63:  (111111) = (1)(1)(1)(1)(1)(1) = (1)(1)(1)(1)(1)(1)
  65: (1000001) =        (1)(000001) = (100000)(1)
  73: (1001001) =      (1)(001)(001) = (100)(100)(1)
  74: (1001010) =      (1)(00101)(0) = (100)(10)(10)
  83: (1010011) =      (1)(01)(0011) = (10100)(1)(1)
		

Crossrefs

The version counting compositions is A329394.

The version ignoring the most significant digit is A329395.

Binary Lyndon/co-Lyndon words are counted by A001037.

Lyndon/co-Lyndon compositions are counted by A059966.

Lyndon compositions whose reverse is not co-Lyndon are A329324.

Binary Lyndon/co-Lyndon words are constructed by A102659 and A329318.

Cf. A060223, A211100, A275692, A328596, A329312, A329313, A329326, A329398.

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,#]]&]]]];
colynQ[q_]:=Array[Union[{RotateRight[q,#],q}]=={RotateRight[q,#],q}&,Length[q]-1,1,And];
colynfac[q_]:=If[Length[q]==0,{},Function[i,Prepend[colynfac[Drop[q,i]],Take[q,i]]]@Last[Select[Range[Length[q]],colynQ[Take[q,#]]&]]];
Select[Range[100],Length[lynfac[IntegerDigits[#,2]]]==Length[colynfac[IntegerDigits[#,2]]]&]

Formula

A211100(a(n)) = A329312(a(n)).