login
A329325
Irregular triangle read by rows where row n gives the lengths of the components in the Lyndon factorization of the binary expansion of n with first digit removed.
13
1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 3, 2, 1, 3, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 3, 1, 4, 2, 1, 1, 2, 2, 3, 1, 4, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 4, 1, 5, 3, 1, 1, 5, 4, 1, 5, 2, 1
OFFSET
1,5
COMMENTS
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).
EXAMPLE
Triangle begins:
1: () 21: (22) 41: (23) 61: (1112)
2: (1) 22: (31) 42: (221) 62: (11111)
3: (1) 23: (4) 43: (5) 63: (11111)
4: (11) 24: (1111) 44: (311) 64: (111111)
5: (2) 25: (13) 45: (32) 65: (6)
6: (11) 26: (121) 46: (41) 66: (51)
7: (11) 27: (13) 47: (5) 67: (6)
8: (111) 28: (1111) 48: (11111) 68: (411)
9: (3) 29: (112) 49: (14) 69: (6)
10: (21) 30: (1111) 50: (131) 70: (51)
11: (3) 31: (1111) 51: (14) 71: (6)
12: (111) 32: (11111) 52: (1211) 72: (3111)
13: (12) 33: (5) 53: (122) 73: (33)
14: (111) 34: (41) 54: (131) 74: (51)
15: (111) 35: (5) 55: (14) 75: (6)
16: (1111) 36: (311) 56: (11111) 76: (411)
17: (4) 37: (5) 57: (113) 77: (6)
18: (31) 38: (41) 58: (1121) 78: (51)
19: (4) 39: (5) 59: (113) 79: (6)
20: (211) 40: (2111) 60: (11111) 80: (21111)
For example, the trimmed binary expansion of 41 is (01001), with Lyndon factorization (01)(001), so row 41 is {2,3}.
MATHEMATICA
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]]&]]]];
Table[Length/@lynfac[Rest[IntegerDigits[n, 2]]], {n, 100}]
CROSSREFS
Row lengths are A211097.
Row sums are A000523.
Keeping the first digit gives A329314.
Positions of singleton rows are A329327.
Binary Lyndon words are counted by A001037 and ranked by A102659.
Numbers whose reversed binary expansion is a Lyndon word are A328596.
Length of the co-Lyndon factorization of the binary expansion is A329312.
Sequence in context: A322482 A231071 A209156 * A341149 A191004 A191358
KEYWORD
nonn,tabf
AUTHOR
Gus Wiseman, Nov 11 2019
STATUS
approved