A329400 Length of the co-Lyndon factorization of the binary expansion of n with the most significant (first) digit removed.

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

Offset

1,4

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

Decapitated binary expansions of 1..20 together with their co-Lyndon factorizations:
   1:     () =
   2:    (0) = (0)
   3:    (1) = (1)
   4:   (00) = (0)(0)
   5:   (01) = (0)(1)
   6:   (10) = (10)
   7:   (11) = (1)(1)
   8:  (000) = (0)(0)(0)
   9:  (001) = (0)(0)(1)
  10:  (010) = (0)(10)
  11:  (011) = (0)(1)(1)
  12:  (100) = (100)
  13:  (101) = (10)(1)
  14:  (110) = (110)
  15:  (111) = (1)(1)(1)
  16: (0000) = (0)(0)(0)(0)
  17: (0001) = (0)(0)(0)(1)
  18: (0010) = (0)(0)(10)
  19: (0011) = (0)(0)(1)(1)
  20: (0100) = (0)(100)

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

Crossrefs

The non-"co" version is A211097.

The version involving all digits is A329312.

Lyndon and co-Lyndon compositions are (both) counted by A059966.

Numbers whose reversed binary expansion is Lyndon are A328596.

Numbers whose binary expansion is co-Lyndon are A275692.

Numbers whose decapitated binary expansion is co-Lyndon are A329401.

Cf. A001037, A060223, A102659, A211100, A329313, A329318, A329326, A329395.

Sequence in context: A256478 A356245 A106638 * A131909 A307319 A131730

Adjacent sequences: A329397 A329398 A329399 * A329401 A329402 A329403

Keyword

nonn

Author

Gus Wiseman, Nov 16 2019

Status

approved