A329326 -id:A329326 - cp's OEIS frontend

A329400 Length of the co-Lyndon factorization of the binary expansion of n with the most significant (first) digit removed.

0, 1, 1, 2, 2, 1, 2, 3, 3, 2, 3, 1, 2, 1, 3, 4, 4, 3, 4, 2, 3, 2, 4, 1, 2, 2, 3, 1, 2, 1, 4, 5, 5, 4, 5, 3, 4, 3, 5, 2, 3, 3, 4, 2, 3, 2, 5, 1, 2, 2, 3, 1, 3, 2, 4, 1, 2, 1, 3, 1, 2, 1, 5, 6, 6, 5, 6, 4, 5, 4, 6, 3, 4, 4, 5, 3, 4, 3, 6, 2, 3, 3, 4, 2, 4, 3, 5

Offset: 1

Gus Wiseman, Nov 16 2019

nonn

The co-Lyndon product of two or more finite sequences is defined to be the lexicographically minimal sequence obtainable by shuffling the sequences together. For example, the co-Lyndon product of (231) and (213) is (212313), the product of (221) and (213) is (212213), and the product of (122) and (2121) is (1212122). A co-Lyndon word is a finite sequence that is prime with respect to the co-Lyndon product. Equivalently, a co-Lyndon word is a finite sequence that is lexicographically strictly greater than all of its cyclic rotations. Every finite sequence has a unique (orderless) factorization into co-Lyndon words, and if these factors are arranged in a certain order, their concatenation is equal to their co-Lyndon product. For example, (1001) has sorted co-Lyndon factorization (1)(100).

			Decapitated binary expansions of 1..20 together with their co-Lyndon factorizations:
   1:     () =
   2:    (0) = (0)
   3:    (1) = (1)
   4:   (00) = (0)(0)
   5:   (01) = (0)(1)
   6:   (10) = (10)
   7:   (11) = (1)(1)
   8:  (000) = (0)(0)(0)
   9:  (001) = (0)(0)(1)
  10:  (010) = (0)(10)
  11:  (011) = (0)(1)(1)
  12:  (100) = (100)
  13:  (101) = (10)(1)
  14:  (110) = (110)
  15:  (111) = (1)(1)(1)
  16: (0000) = (0)(0)(0)(0)
  17: (0001) = (0)(0)(0)(1)
  18: (0010) = (0)(0)(10)
  19: (0011) = (0)(0)(1)(1)
  20: (0100) = (0)(100)

The non-"co" version is A211097.
The version involving all digits is A329312.
Lyndon and co-Lyndon compositions are (both) counted by A059966.
Numbers whose reversed binary expansion is Lyndon are A328596.
Numbers whose binary expansion is co-Lyndon are A275692.
Numbers whose decapitated binary expansion is co-Lyndon are A329401.
Cf. A001037, A060223, A102659, A211100, A329313, A329318, A329326, A329395.

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,#]]&]]];
Table[If[n==0,0,Length[colynfac[Rest[IntegerDigits[n,2]]]]],{n,30}]

A329401 Numbers whose binary expansion without the most significant (first) digit is a co-Lyndon word.

Original entry on oeis.org

2, 3, 6, 12, 14, 24, 28, 30, 48, 52, 56, 58, 60, 62, 96, 104, 112, 114, 116, 120, 122, 124, 126, 192, 200, 208, 212, 224, 226, 228, 232, 234, 236, 240, 242, 244, 246, 248, 250, 252, 254, 384, 400, 416, 420, 424, 448, 450, 452, 456, 458, 464, 466, 468, 472, 474

Offset: 1

Gus Wiseman, Nov 16 2019

nonn

A co-Lyndon word is a finite sequence that is lexicographically strictly greater than all of its cyclic rotations.

			The sequence of terms together with their binary expansions begins:
    2: (1,0)
    3: (1,1)
    6: (1,1,0)
   12: (1,1,0,0)
   14: (1,1,1,0)
   24: (1,1,0,0,0)
   28: (1,1,1,0,0)
   30: (1,1,1,1,0)
   48: (1,1,0,0,0,0)
   52: (1,1,0,1,0,0)
   56: (1,1,1,0,0,0)
   58: (1,1,1,0,1,0)
   60: (1,1,1,1,0,0)
   62: (1,1,1,1,1,0)
   96: (1,1,0,0,0,0,0)
  104: (1,1,0,1,0,0,0)
  112: (1,1,1,0,0,0,0)
  114: (1,1,1,0,0,1,0)
  116: (1,1,1,0,1,0,0)
  120: (1,1,1,1,0,0,0)

The version involving all digits is A275692.
Binary Lyndon/co-Lyndon words are A001037.
A ranking of binary co-Lyndon words is A329318
Cf. A059966, A060223, A102659, A211097, A211100, A328594, A328596, A329312, A329325, A329326, A329359, A329395, A329396, A329400.

colynQ[q_]:=Array[Union[{RotateRight[q,#],q}]=={RotateRight[q,#],q}&,Length[q]-1,1,And];
Select[Range[2,100],colynQ[Rest[IntegerDigits[#,2]]]&]

A329357 Numbers whose reversed binary expansion has co-Lyndon factorization of length 2.

Original entry on oeis.org

2, 3, 5, 9, 11, 17, 19, 23, 33, 35, 37, 39, 43, 47, 65, 67, 69, 71, 75, 79, 83, 87, 95, 129, 131, 133, 135, 137, 139, 143, 147, 149, 151, 155, 159, 163, 167, 171, 175, 183, 191, 257, 259, 261, 263, 265, 267, 271, 275, 277, 279, 283, 287, 291, 293, 295, 299

Offset: 1

Gus Wiseman, Nov 12 2019

nonn

First differs from A329327 in lacking 77 and having 83.

			The reversed binary expansion of each term together with their co-Lyndon factorizations:
   2:      (01) = (0)(1)
   3:      (11) = (1)(1)
   5:     (101) = (10)(1)
   9:    (1001) = (100)(1)
  11:    (1101) = (110)(1)
  17:   (10001) = (1000)(1)
  19:   (11001) = (1100)(1)
  23:   (11101) = (1110)(1)
  33:  (100001) = (10000)(1)
  35:  (110001) = (11000)(1)
  37:  (101001) = (10100)(1)
  39:  (111001) = (11100)(1)
  43:  (110101) = (11010)(1)
  47:  (111101) = (11110)(1)
  65: (1000001) = (100000)(1)
  67: (1100001) = (110000)(1)
  69: (1010001) = (101000)(1)
  71: (1110001) = (111000)(1)
  75: (1101001) = (110100)(1)
  79: (1111001) = (111100)(1)

Positions of 2's in A329326.
Binary co-Lyndon words are counted by A001037 and ranked by A329318.
Length of the co-Lyndon factorization of the binary expansion is A329312.
Cf. A059966, A060223, A102659, A211097, A211100, A275692, A328594, A328595, A328596, A329131, A329313, A329314, A329325, A329359.

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[colynfac[Reverse[IntegerDigits[#,2]]]]==2&]

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

Original entry on oeis.org

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

Gus Wiseman, Nov 15 2019

nonn

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

			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)

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.

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]]]&]

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

cp's OEIS Frontend

A329400 Length of the co-Lyndon factorization of the binary expansion of n with the most significant (first) digit removed.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A329401 Numbers whose binary expansion without the most significant (first) digit is a co-Lyndon word.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A329357 Numbers whose reversed binary expansion has co-Lyndon factorization of length 2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula