cp's OEIS Frontend

A318728 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.

%I A318728 #15 Nov 04 2019 09:20:34
%S A318728 1,2,3,4,6,9,13,22,34,58,95,168,280,492,853,1508,2648,4715,8350,14924,
%T A318728 26643,47794,85779,154475,278323,502716,908913,1646206,2984547,
%U A318728 5418653,9847190,17916001,32625618,59470540,108493150,198094483,361965239,661891580,1211162271
%N A318728 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 A318728 Andrew Howroyd, <a href="/A318728/b318728.txt">Table of n, a(n) for n = 1..100</a>
%F A318728 a(n) = A328597(n) + 1 for n > 1. - _Andrew Howroyd_, Oct 27 2019
%e A318728 The a(7) = 13 cyclic compositions with adjacent parts coprime:
%e A318728   7,
%e A318728   16, 25, 34,
%e A318728   115,
%e A318728   1114, 1213, 1132, 1123,
%e A318728   11113, 11212,
%e A318728   111112,
%e A318728   1111111.
%t A318728 neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];
%t A318728 Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Or[Length[#]==1,neckQ[#]&&And@@CoprimeQ@@@Partition[#,2,1,1]]&]],{n,20}]
%o A318728 (PARI)
%o A318728 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 A318728 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 A318728 Cf. A000740, A000837, A008965, A059966, A100953, A167606, A296302, A318726, A318727, A328597.
%K A318728 nonn
%O A318728 1,2
%A A318728 _Gus Wiseman_, Sep 02 2018
%E A318728 Terms a(21) and beyond from _Andrew Howroyd_, Sep 08 2018
%E A318728 Name corrected by _Gus Wiseman_, Nov 04 2019