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,4

Links

Table of n, a(n) for n=1..35.

Formula

Moebius transform of A059966. Second Moebius transform of A008965.

Example

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.

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}]

Crossrefs

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

Sequence in context: A066028 A066039 A142341 * A256062 A303677 A303802

Adjacent sequences: A318728 A318729 A318730 * A318732 A318733 A318734

Keyword

nonn

Author

Gus Wiseman, Sep 02 2018

Status

approved