A329359 - OEIS

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.

%I #14 Feb 20 2020 13:55:19

%S 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,

%T 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,

%U 1,3,3,3,2,1,3,3,3,1,1,1,6,5,1,2,2,2,2

%N 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.

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

%e Triangle begins:

%e 1: (1) 21: (221) 41: (51) 61: (51)

%e 2: (2) 22: (23) 42: (222) 62: (6)

%e 3: (11) 23: (2111) 43: (2211) 63: (111111)

%e 4: (3) 24: (5) 44: (24) 64: (7)

%e 5: (21) 25: (41) 45: (231) 65: (61)

%e 6: (3) 26: (5) 46: (24) 66: (52)

%e 7: (111) 27: (311) 47: (21111) 67: (511)

%e 8: (4) 28: (5) 48: (6) 68: (43)

%e 9: (31) 29: (41) 49: (51) 69: (421)

%e 10: (22) 30: (5) 50: (6) 70: (43)

%e 11: (211) 31: (11111) 51: (411) 71: (4111)

%e 12: (4) 32: (6) 52: (6) 72: (7)

%e 13: (31) 33: (51) 53: (51) 73: (331)

%e 14: (4) 34: (42) 54: (33) 74: (322)

%e 15: (1111) 35: (411) 55: (3111) 75: (3211)

%e 16: (5) 36: (33) 56: (6) 76: (34)

%e 17: (41) 37: (321) 57: (51) 77: (331)

%e 18: (32) 38: (33) 58: (6) 78: (34)

%e 19: (311) 39: (3111) 59: (411) 79: (31111)

%e 20: (5) 40: (6) 60: (6) 80: (7)

%e For example, 45 has binary expansion (101101), with co-Lyndon factorization (10)(110)(1), so row n = 45 is (2,3,1).

%t colynQ[q_]:=Array[Union[{RotateRight[q,#],q}]=={RotateRight[q,#],q}&,Length[q]-1,1,And];

%t colynfac[q_]:=If[Length[q]==0,{},Function[i,Prepend[colynfac[Drop[q,i]],Take[q,i]]]@Last[Select[Range[Length[q]],colynQ[Take[q,#]]&]]];

%t Table[Length/@colynfac[If[n==0,{},IntegerDigits[n,2]]],{n,30}]

%Y Row lengths are A329312.

%Y Row sums are A070939.

%Y Positions of rows of length 1 are A275692.

%Y The non-"co" version is A329314.

%Y Binary co-Lyndon words are counted by A001037 and ranked by A329318.

%Y Cf. A059966, A211097, A211100, A328596, A296372, A329313, A329315, A329325, A329357.

%K nonn,tabf

%O 1,2

%A _Gus Wiseman_, Nov 12 2019