login
A318731
Number of relatively prime Lyndon compositions (aperiodic necklaces of positive integers) with sum n.
11
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
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
KEYWORD
nonn
AUTHOR
Gus Wiseman, Sep 02 2018
STATUS
approved