|
%I #15 Nov 04 2019 09:20:34
%S 1,2,3,4,6,9,13,22,34,58,95,168,280,492,853,1508,2648,4715,8350,14924,
%T 26643,47794,85779,154475,278323,502716,908913,1646206,2984547,
%U 5418653,9847190,17916001,32625618,59470540,108493150,198094483,361965239,661891580,1211162271
%N Number of cyclic compositions (necklaces of positive integers) summing to n that have only one part or whose adjacent parts (including the last with first) are coprime.
%H Andrew Howroyd, <a href="/A318728/b318728.txt">Table of n, a(n) for n = 1..100</a>
%F a(n) = A328597(n) + 1 for n > 1. - _Andrew Howroyd_, Oct 27 2019
%e The a(7) = 13 cyclic compositions with adjacent parts coprime:
%e 7,
%e 16, 25, 34,
%e 115,
%e 1114, 1213, 1132, 1123,
%e 11113, 11212,
%e 111112,
%e 1111111.
%t neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];
%t Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Or[Length[#]==1,neckQ[#]&&And@@CoprimeQ@@@Partition[#,2,1,1]]&]],{n,20}]
%o (PARI)
%o b(n, q, pred)={my(M=matrix(n, n)); for(k=1, n, M[k, k]=pred(q, k); for(i=1, k-1, M[i, k]=sum(j=1, k-i, if(pred(j, i), M[j, k-i], 0)))); M[q,]}
%o seq(n)={my(v=sum(k=1, n, k*b(n, k, (i,j)->gcd(i,j)==1))); vector(n, n, (n > 1) + sumdiv(n, d, eulerphi(d)*v[n/d])/n)} \\ _Andrew Howroyd_, Oct 27 2019
%Y Cf. A000740, A000837, A008965, A059966, A100953, A167606, A296302, A318726, A318727, A328597.
%K nonn
%O 1,2
%A _Gus Wiseman_, Sep 02 2018
%E Terms a(21) and beyond from _Andrew Howroyd_, Sep 08 2018
%E Name corrected by _Gus Wiseman_, Nov 04 2019
|
