A329313 -id:A329313 - cp's OEIS frontend

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

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

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

A329359 Irregular triangle read by rows where row n gives the lengths of the factors in the co-Lyndon factorization of the binary expansion of n.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Nov 12 2019

			Triangle begins:
   1: (1)       21: (221)      41: (51)       61: (51)
   2: (2)       22: (23)       42: (222)      62: (6)
   3: (11)      23: (2111)     43: (2211)     63: (111111)
   4: (3)       24: (5)        44: (24)       64: (7)
   5: (21)      25: (41)       45: (231)      65: (61)
   6: (3)       26: (5)        46: (24)       66: (52)
   7: (111)     27: (311)      47: (21111)    67: (511)
   8: (4)       28: (5)        48: (6)        68: (43)
   9: (31)      29: (41)       49: (51)       69: (421)
  10: (22)      30: (5)        50: (6)        70: (43)
  11: (211)     31: (11111)    51: (411)      71: (4111)
  12: (4)       32: (6)        52: (6)        72: (7)
  13: (31)      33: (51)       53: (51)       73: (331)
  14: (4)       34: (42)       54: (33)       74: (322)
  15: (1111)    35: (411)      55: (3111)     75: (3211)
  16: (5)       36: (33)       56: (6)        76: (34)
  17: (41)      37: (321)      57: (51)       77: (331)
  18: (32)      38: (33)       58: (6)        78: (34)
  19: (311)     39: (3111)     59: (411)      79: (31111)
  20: (5)       40: (6)        60: (6)        80: (7)
For example, 45 has binary expansion (101101), with co-Lyndon factorization (10)(110)(1), so row n = 45 is (2,3,1).

Row lengths are A329312.
Row sums are A070939.
Positions of rows of length 1 are A275692.
The non-"co" version is A329314.
Binary co-Lyndon words are counted by A001037 and ranked by A329318.
Cf. A059966, A211097, A211100, A328596, A296372, A329313, A329315, A329325, A329357.

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[Length/@colynfac[If[n==0,{},IntegerDigits[n,2]]],{n,30}]

A348268 Mapping between Lyndon factorization and prime factorization.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 11, 10, 9, 12, 13, 14, 17, 16, 19, 22, 15, 20, 29, 18, 21, 24, 23, 26, 37, 28, 31, 34, 41, 32, 43, 38, 33, 44, 25, 30, 35, 40, 53, 58, 27, 36, 67, 42, 51, 48, 47, 46, 39, 52, 61, 74, 49, 56, 59, 62, 73, 68, 71, 82, 79, 64, 83, 86, 57, 76, 55, 66, 77

Offset: 0

Thomas Scheuerle, Oct 09 2021

A Lyndon word is a finite sequence that is lexicographically strictly less than all of its cyclic rotations.
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. 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).
We use Lyndon factorization on the reversed order binary expansion of n, then we use the mapping from Lyndon words (A328596(k) reversed binary expansion) to positive integers that have no divisors other than 1 and itself (A008578(k+1)). a(n) has factors in A008578 as the binary expansion of n has in A328596.

			We map Lyndon-words to positive integers that have no divisors other than 1 and itself: [] -> 1, 1 -> 2, 01 -> 3, 001 -> 5, 011 -> 7, 0001 -> 11, ...
9 is in reversed order binary: 1001, has the factors (1)(001) -> a(9) = 2*5 = 10.
10 is in reversed order binary: 0101, has the factors (01)(01) -> a(10) = 3*3 = 9.

Thomas Scheuerle, Table of n, a(n) for n = 0..5000
Thomas Scheuerle, Program (MATLAB)
Index entries for sequences that are permutations of the natural numbers

Cf. A329313, A328596, A008578, A329399, A000961, A328595, A328595.

MATLAB
```
% See Scheuerle link.
```

a(Lyndonproduct(n,m)) = a(n)*a(m).
a(1 + 2*n)/a(n) = 2.
all a(A329399(n)) are in A000961 (powers of primes).
all a(A328595(n)) (reversed binary expansion is a necklace) are in A329131 (prime signature is a Lyndon word).

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

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A329359 Irregular triangle read by rows where row n gives the lengths of the factors in the co-Lyndon factorization of the binary expansion of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A348268 Mapping between Lyndon factorization and prime factorization.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

MATLAB

Formula

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula