A329314 Irregular triangle read by rows where row n gives the lengths of the components in the Lyndon factorization of the binary expansion of n.

1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 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, 1, 4, 1, 3, 1, 1, 4, 1, 2, 1, 1, 1, 2, 2, 1, 3, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 2, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1

Offset

0,10

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

Links

Table of n, a(n) for n=0..86.

Example

Triangle begins:
   0: ()         20: (1211)      40: (12111)     60: (111111)
   1: (1)        21: (122)       41: (123)       61: (11112)
   2: (11)       22: (131)       42: (1221)      62: (111111)
   3: (11)       23: (14)        43: (15)        63: (111111)
   4: (111)      24: (11111)     44: (1311)      64: (1111111)
   5: (12)       25: (113)       45: (132)       65: (16)
   6: (111)      26: (1121)      46: (141)       66: (151)
   7: (111)      27: (113)       47: (15)        67: (16)
   8: (1111)     28: (11111)     48: (111111)    68: (1411)
   9: (13)       29: (1112)      49: (114)       69: (16)
  10: (121)      30: (11111)     50: (1131)      70: (151)
  11: (13)       31: (11111)     51: (114)       71: (16)
  12: (1111)     32: (111111)    52: (11211)     72: (13111)
  13: (112)      33: (15)        53: (1122)      73: (133)
  14: (1111)     34: (141)       54: (1131)      74: (151)
  15: (1111)     35: (15)        55: (114)       75: (16)
  16: (11111)    36: (1311)      56: (111111)    76: (1411)
  17: (14)       37: (15)        57: (1113)      77: (16)
  18: (131)      38: (141)       58: (11121)     78: (151)
  19: (14)       39: (15)        59: (1113)      79: (16)

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[If[n==0, {}, IntegerDigits[n, 2]]], {n, 0, 50}]

Crossrefs

Row lengths are A211100.

Row sums are A029837, or, if the first term is 1, A070939.

Ignoring the first digit gives A329325.

Positions of rows of length 2 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.

Cf. A059966, A211097, A275692, A296372, A329313, A329315, A329318.

Sequence in context: A086251 A374381 A177121 * A092931 A147300 A346481

Adjacent sequences: A329311 A329312 A329313 * A329315 A329316 A329317

Keyword

nonn,tabf

Author

Gus Wiseman, Nov 11 2019

Status

approved