A329313 Length of the Lyndon factorization of the reversed binary expansion of n.

0, 1, 1, 2, 1, 2, 1, 3, 1, 2, 2, 3, 1, 2, 1, 4, 1, 2, 2, 3, 1, 3, 2, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 2, 3, 2, 3, 2, 4, 1, 2, 3, 4, 1, 3, 2, 5, 1, 2, 2, 3, 1, 2, 2, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 2, 3, 2, 3, 2, 4, 1, 3, 3, 4, 2, 3, 2, 5, 1, 2, 2, 3, 1, 4, 3

Offset

0,4

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

Links

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

Example

The sequence of reversed binary expansions of the nonnegative integers together with their Lyndon factorizations begins:
   0:      () = ()
   1:     (1) = (1)
   2:    (01) = (01)
   3:    (11) = (1)(1)
   4:   (001) = (001)
   5:   (101) = (1)(01)
   6:   (011) = (011)
   7:   (111) = (1)(1)(1)
   8:  (0001) = (0001)
   9:  (1001) = (1)(001)
  10:  (0101) = (01)(01)
  11:  (1101) = (1)(1)(01)
  12:  (0011) = (0011)
  13:  (1011) = (1)(011)
  14:  (0111) = (0111)
  15:  (1111) = (1)(1)(1)(1)
  16: (00001) = (00001)
  17: (10001) = (1)(0001)
  18: (01001) = (01)(001)
  19: (11001) = (1)(1)(001)
  20: (00101) = (00101)

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[If[n==0, 0, Length[lynfac[Reverse[IntegerDigits[n, 2]]]]], {n, 0, 30}]

Crossrefs

The non-reversed version is A211100.

Positions of 1's are A328596.

The "co" version is A329326.

Binary Lyndon words are counted by A001037 and ranked by A102659.

Numbers whose reversed binary expansion is a necklace are A328595.

Numbers whose reversed binary expansion is a aperiodic are A328594.

Length of the co-Lyndon factorization of the binary expansion is A329312.

Cf. A000031, A027375, A059966, A060223, A121016, A211097, A275692, A329131, A329314, A329317, A329325.

Sequence in context: A263280 A136107 A178691 * A329312 A211271 A124768

Adjacent sequences: A329310 A329311 A329312 * A329314 A329315 A329316

Keyword

nonn

Author

Gus Wiseman, Nov 11 2019

Status

approved