cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

A211097 Number of factors in Lyndon factorization of binary vectors of lengths 1, 2, 3, ...

This page as a plain text file.
%I A211097 #29 Mar 30 2023 09:16:19
%S A211097 1,1,2,1,2,2,3,1,2,1,3,2,3,3,4,1,2,1,3,2,2,1,4,2,3,2,4,3,4,4,5,1,2,1,
%T A211097 3,1,2,1,4,2,3,1,3,2,2,1,5,2,3,2,4,3,3,2,5,3,4,3,5,4,5,5,6,1,2,1,3,1,
%U A211097 2,1,4,2,2,1,3,1,2,1,5,2,3,2,4,3,2,1,4,2,3,2,3,2,2,1,6,2,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
%N A211097 Number of factors in Lyndon factorization of binary vectors of lengths 1, 2, 3, ...
%C A211097 Any binary word has a unique factorization as a product of nonincreasing Lyndon words (see Lothaire). Here we look at the Lyndon factorizations of the binary vectors 0,1, 00,01,10,11, 000,001,010,011,100,101,110,111, 0000,...
%C A211097 For the largest (or leftmost) factor see A211098, A211099.
%C A211097 The smallest (or rightmost) factors are given by A211095 and A211096, offset by 2.
%D A211097 M. Lothaire, Combinatorics on Words, Addison-Wesley, Reading, MA, 1983. See Theorem 5.1.5, p. 67.
%D A211097 G. Melançon, Factorizing infinite words using Maple, MapleTech Journal, vol. 4, no. 1, 1997, pp. 34-42
%H A211097 N. J. A. Sloane, <a href="/A211097/b211097.txt">Table of n, a(n) for n = 1..10000</a>
%H A211097 N. J. A. Sloane, <a href="/A211097/a211097.txt">Maple programs for A211097 etc.</a>
%e A211097 Here are the Lyndon factorizations of the first few binary vectors:
%e A211097 .0.
%e A211097 .1.
%e A211097 .0.0.
%e A211097 .01.
%e A211097 .1.0.
%e A211097 .1.1.
%e A211097 .0.0.0.
%e A211097 .001.
%e A211097 .01.0. <- this means that the factorization is (01)(0), for example
%e A211097 .011.
%e A211097 .1.0.0.
%e A211097 .1.01.
%e A211097 .1.1.0.
%e A211097 .1.1.1.
%e A211097 .0.0.0.0.
%e A211097 ...
%t A211097 lynQ[q_]:=Array[Union[{q,RotateRight[q,#]}]=={q,RotateRight[q,#]}&,Length[q]-1,1,And];
%t A211097 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 A211097 Table[Length[lynfac[Rest[IntegerDigits[n,2]]]],{n,2,50}] (* _Gus Wiseman_, Nov 14 2019 *)
%Y A211097 A211098 and A211099 give information about the largest (or leftmost) factor.
%Y A211097 Cf. A211095, A211096.
%Y A211097 Row-lengths of A329325.
%Y A211097 The "co" version is A329400.
%Y A211097 Retaining the first digit gives A211100.
%Y A211097 Binary Lyndon words are counted by A001037 and constructed by A102659.
%Y A211097 Numbers whose reversed binary expansion is Lyndon are A328596.
%Y A211097 Cf. A059966, A060223, A275692, A329312, A329313, A329314, A329326.
%K A211097 nonn
%O A211097 1,3
%A A211097 _N. J. A. Sloane_, Apr 01 2012