login
Number of relatively prime Lyndon compositions (aperiodic necklaces of positive integers) with sum n.
11

%I #4 Sep 02 2018 17:09:02

%S 1,0,1,2,5,7,17,27,54,93,185,324,629,1143,2175,4050,7709,14469,27593,

%T 52276,99839,190371,364721,698508,1342170,2580165,4970952,9585232,

%U 18512789,35787985,69273665,134211600,260300799,505278705,981706783

%N Number of relatively prime Lyndon compositions (aperiodic necklaces of positive integers) with sum n.

%F Moebius transform of A059966. Second Moebius transform of A008965.

%e The a(6) = 7 relatively prime Lyndon compositions are 15, 114, 132, 123, 1113, 1122, 11112.

%e The a(7) = 17 relatively prime Lyndon compositions:

%e 16, 25, 34,

%e 115, 142, 124, 133, 223,

%e 1114, 1213, 1132, 1123, 1222,

%e 11113, 11212, 11122,

%e 111112.

%t LyndonQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]&&Array[RotateRight[q,#]&,Length[q],1,UnsameQ];

%t Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],LyndonQ[#]&&GCD@@#==1&]],{n,10}]

%Y Cf. A000740, A000837, A008965, A059966, A100953, A296302.

%K nonn

%O 1,4

%A _Gus Wiseman_, Sep 02 2018