cp's OEIS Frontend

A211100 Number of factors in Lyndon factorization of binary expansion of n.

%I A211100 #40 Mar 30 2023 06:15:05
%S A211100 1,1,2,2,3,2,3,3,4,2,3,2,4,3,4,4,5,2,3,2,4,3,3,2,5,3,4,3,5,4,5,5,6,2,
%T A211100 3,2,4,2,3,2,5,3,4,2,4,3,3,2,6,3,4,3,5,4,4,3,6,4,5,4,6,5,6,6,7,2,3,2,
%U A211100 4,2,3,2,5,3,3,2,4,2,3,2,6,3,4,3,5,4,3,2,5,3,4,3,4,3,3,2,7,3,4,3,5,3,4,3,6,4,5,3,5,4,4,3,7,4,5,4,6,5,5,4,7
%N A211100 Number of factors in Lyndon factorization of binary expansion of n.
%C A211100 Any binary word has a unique factorization as a product of nonincreasing Lyndon words (see Lothaire). a(n) = number of factors in Lyndon factorization of binary expansion of n.
%C A211100 It appears that a(n) = k for the first time when n = 2^(k-1)+1.
%C A211100 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. - _Gus Wiseman_, Nov 12 2019
%D A211100 M. Lothaire, Combinatorics on Words, Addison-Wesley, Reading, MA, 1983. See Theorem 5.1.5, p. 67.
%D A211100 G. Melançon, Factorizing infinite words using Maple, MapleTech Journal, vol. 4, no. 1, 1997, pp. 34-42
%H A211100 N. J. A. Sloane, <a href="/A211100/b211100.txt">Table of n, a(n) for n = 0..10000</a>
%H A211100 N. J. A. Sloane, <a href="/A211100/a211100_1.txt">Maple programs for A211100 etc.</a>
%e A211100 n=25 has binary expansion 11001, which has Lyndon factorization (1)(1)(001) with three factors, so a(25) = 3.
%e A211100 Here are the Lyndon factorizations for small values of n:
%e A211100 .0.
%e A211100 .1.
%e A211100 .1.0.
%e A211100 .1.1.
%e A211100 .1.0.0.
%e A211100 .1.01.
%e A211100 .1.1.0.
%e A211100 .1.1.1.
%e A211100 .1.0.0.0.
%e A211100 .1.001.
%e A211100 .1.01.0.
%e A211100 .1.011.
%e A211100 .1.1.0.0.
%e A211100 ...
%t A211100 lynQ[q_]:=Array[Union[{q,RotateRight[q,#]}]=={q,RotateRight[q,#]}&,Length[q]-1,1,And];
%t A211100 lynfac[q_]:=If[Length[q]==0,{},Function[i,Prepend[lynfac[Drop[q,i]],Take[q,i]]][Last[Select[Range[Length[q]],lynQ[Take[q,#]]&]]]];
%t A211100 Table[Length[lynfac[IntegerDigits[n,2]]],{n,0,30}] (* _Gus Wiseman_, Nov 12 2019 *)
%Y A211100 Cf. A001037 (number of Lyndon words of length m); A102659 (list thereof).
%Y A211100 A211095 and A211096 give information about the smallest (or rightmost) factor. Cf. A211097, A211098, A211099.
%Y A211100 Row-lengths of A329314.
%Y A211100 The "co-" version is A329312.
%Y A211100 Positions of 2's are A329327.
%Y A211100 The reversed version is A329313.
%Y A211100 The inverted version is A329312.
%Y A211100 Ignoring the first digit gives A211097.
%Y A211100 Cf. A059966, A060223, A275692, A296658, A328594, A328595, A328596, A329131, A329325, A329326.
%K A211100 nonn
%O A211100 0,3
%A A211100 _N. J. A. Sloane_, Mar 31 2012