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

1, 0, 1, 2, 5, 7, 17, 27, 54, 93, 185, 324, 629, 1143, 2175, 4050, 7709, 14469, 27593, 52276, 99839, 190371, 364721, 698508, 1342170, 2580165, 4970952, 9585232, 18512789, 35787985, 69273665, 134211600, 260300799, 505278705, 981706783

Offset: 1

Author

Gus Wiseman, Sep 02 2018

Keywords

• nonn

Examples

			The a(6) = 7 relatively prime Lyndon compositions are 15, 114, 132, 123, 1113, 1122, 11112.
The a(7) = 17 relatively prime Lyndon compositions:
  16, 25, 34,
  115, 142, 124, 133, 223,
  1114, 1213, 1132, 1123, 1222,
  11113, 11212, 11122,
  111112.
		

Crossrefs

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

Programs

Mathematica

LyndonQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]&&Array[RotateRight[q,#]&,Length[q],1,UnsameQ];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],LyndonQ[#]&&GCD@@#==1&]],{n,10}]

Formula

Moebius transform of A059966. Second Moebius transform of A008965.