Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.
%I #6 Nov 11 2019 21:38:04
%S 1,2,3,2,2,3,3,4,5,4,5,6,5,3,4,4,2,3,4,3,4,3,3,4,4,5,6,5,4,5,5,2,3,3,
%T 4,5,4,5,6,5,3,4,4,5,6,5,6,5,3,4,4,2,3,4,3,4,5,4,3,4,4,5,6,5,6,7,6,4,
%U 5,5,3,4,4,5,6,5,6,5,4,5,6,5,6,7,6,5,6
%N Length of the Lyndon factorization of the reversed first n terms of A000002.
%C 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).
%e The sequence of Lyndon factorizations of the reversed initial terms of A000002 begins:
%e 1: (1)
%e 2: (2)(1)
%e 3: (2)(2)(1)
%e 4: (122)(1)
%e 5: (1122)(1)
%e 6: (2)(1122)(1)
%e 7: (12)(1122)(1)
%e 8: (2)(12)(1122)(1)
%e 9: (2)(2)(12)(1122)(1)
%e 10: (122)(12)(1122)(1)
%e 11: (2)(122)(12)(1122)(1)
%e 12: (2)(2)(122)(12)(1122)(1)
%e 13: (122)(122)(12)(1122)(1)
%e 14: (112212212)(1122)(1)
%e 15: (2)(112212212)(1122)(1)
%e 16: (12)(112212212)(1122)(1)
%e 17: (1121122122121122)(1)
%e 18: (2)(1121122122121122)(1)
%e 19: (2)(2)(1121122122121122)(1)
%e 20: (122)(1121122122121122)(1)
%e For example, the reversed first 13 terms of A000002 are (1221221211221), with Lyndon factorization (122)(122)(12)(1122)(1), so a(13) = 5.
%t lynQ[q_]:=Array[Union[{q,RotateRight[q,#]}]=={q,RotateRight[q,#]}&,Length[q]-1,1,And];
%t 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 kolagrow[q_]:=If[Length[q]<2,Take[{1,2},Length[q]+1],Append[q,Switch[{q[[Length[Split[q]]]],q[[-2]],Last[q]},{1,1,1},0,{1,1,2},1,{1,2,1},2,{1,2,2},0,{2,1,1},2,{2,1,2},2,{2,2,1},1,{2,2,2},1]]]
%t kol[n_Integer]:=Nest[kolagrow,{1},n-1];
%t Table[Length[lynfac[Reverse[kol[n]]]],{n,100}]
%Y Row-lengths of A329316.
%Y The non-reversed version is A329315.
%Y Cf. A000002, A000031, A001037, A027375, A059966, A060223, A088568, A102659, A211100, A288605, A296372, A296658, A329314, A329325.
%K nonn
%O 1,2
%A _Gus Wiseman_, Nov 11 2019