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.

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,2

Comments

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

Links

Table of n, a(n) for n=1..87.

Example

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

Mathematica

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

Crossrefs

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.

Sequence in context: A367680 A152538 A345033 * A235682 A324830 A141110

Adjacent sequences: A329356 A329357 A329358 * A329360 A329361 A329362

Keyword

nonn,tabf

Author

Gus Wiseman, Nov 12 2019

Status

approved