A329357 -id:A329357 - cp's OEIS frontend

A329326 Length of the co-Lyndon factorization of the reversed binary expansion of n.

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

Offset: 1

Gus Wiseman, Nov 11 2019

nonn

First differs from A211100 at a(77) = 3, A211100(77) = 2. The reversed binary expansion of 77 is (1011001), with co-Lyndon factorization (10)(1100)(1), while the binary expansion is (1001101), with Lyndon factorization of (1)(001101).

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 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 positive integer together with their co-Lyndon factorizations begins:
   1:     (1) = (1)
   2:    (01) = (0)(1)
   3:    (11) = (1)(1)
   4:   (001) = (0)(0)(1)
   5:   (101) = (10)(1)
   6:   (011) = (0)(1)(1)
   7:   (111) = (1)(1)(1)
   8:  (0001) = (0)(0)(0)(1)
   9:  (1001) = (100)(1)
  10:  (0101) = (0)(10)(1)
  11:  (1101) = (110)(1)
  12:  (0011) = (0)(0)(1)(1)
  13:  (1011) = (10)(1)(1)
  14:  (0111) = (0)(1)(1)(1)
  15:  (1111) = (1)(1)(1)(1)
  16: (00001) = (0)(0)(0)(0)(1)
  17: (10001) = (1000)(1)
  18: (01001) = (0)(100)(1)
  19: (11001) = (1100)(1)
  20: (00101) = (0)(0)(10)(1)

The non-"co" version is A211100.
Positions of 2's are A329357.
Numbers whose binary expansion is co-Lyndon are A275692.
Length of the co-Lyndon factorization of the binary expansion is A329312.
Cf. A000031, A001037, A059966, A060223, A211097, A296372, A296658, A328596, A329131, A329314, A329318, A329324, A329325.

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[Reverse[IntegerDigits[n,2]]]],{n,100}]

A329327 Numbers whose binary expansion has Lyndon factorization of length 2 (the minimum for n > 1).

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Nov 12 2019

nonn

First differs from A329357 in having 77 and lacking 83.

Also numbers whose decapitated binary expansion is a Lyndon word (see also A329401).

			The binary expansion of each term together with its Lyndon factorization begins:
   2:      (10) = (1)(0)
   3:      (11) = (1)(1)
   5:     (101) = (1)(01)
   9:    (1001) = (1)(001)
  11:    (1011) = (1)(011)
  17:   (10001) = (1)(0001)
  19:   (10011) = (1)(0011)
  23:   (10111) = (1)(0111)
  33:  (100001) = (1)(00001)
  35:  (100011) = (1)(00011)
  37:  (100101) = (1)(00101)
  39:  (100111) = (1)(00111)
  43:  (101011) = (1)(01011)
  47:  (101111) = (1)(01111)
  65: (1000001) = (1)(000001)
  67: (1000011) = (1)(000011)
  69: (1000101) = (1)(000101)
  71: (1000111) = (1)(000111)
  75: (1001011) = (1)(001011)
  77: (1001101) = (1)(001101)

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

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,#1]]&]]]];
Select[Range[100],Length[lynfac[IntegerDigits[#,2]]]==2&]

a(n) = A339608(n) + 1. - Harald Korneliussen, Mar 12 2020

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

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

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

cp's OEIS Frontend

A329326 Length of the co-Lyndon factorization of the reversed binary expansion of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A329327 Numbers whose binary expansion has Lyndon factorization of length 2 (the minimum for n > 1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

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