cp's OEIS Frontend

A328602 Number of necklace compositions of n where no pair of circularly adjacent parts is relatively prime.

%I A328602 #13 Oct 27 2019 05:01:24
%S A328602 0,1,1,2,1,4,1,5,3,8,1,16,1,20,9,35,2,69,3,111,24,190,13,384,31,646,
%T A328602 102,1212,113,2348,227,4254,613,7993,976,15459,1915,28825,4357,54988,
%U A328602 7868,105826,15760,201115,33376,385590,63974,744446,128224,1428047,262914,2754037
%N A328602 Number of necklace compositions of n where no pair of circularly adjacent parts is relatively prime.
%C A328602 A necklace composition of n (A008965) is a finite sequence of positive integers summing to n that is lexicographically minimal among all of its cyclic rotations.
%C A328602 Circularity means the last part is followed by the first.
%H A328602 Andrew Howroyd, <a href="/A328602/b328602.txt">Table of n, a(n) for n = 1..200</a>
%e A328602 The a(2) = 1 through a(10) = 8 necklace compositions:
%e A328602   (2)  (3)  (4)    (5)  (6)      (7)  (8)        (9)      (10)
%e A328602             (2,2)       (2,4)         (2,6)      (3,6)    (2,8)
%e A328602                         (3,3)         (4,4)      (3,3,3)  (4,6)
%e A328602                         (2,2,2)       (2,2,4)             (5,5)
%e A328602                                       (2,2,2,2)           (2,2,6)
%e A328602                                                           (2,4,4)
%e A328602                                                           (2,2,2,4)
%e A328602                                                           (2,2,2,2,2)
%e A328602 The a(19) = 3 necklace compositions are: (19), (3,6,4,6), (2,2,6,3,6).
%t A328602 neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];
%t A328602 Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],neckQ[#]&&And@@Not/@CoprimeQ@@@Partition[#,2,1,1]&]],{n,10}]
%o A328602 (PARI)
%o A328602 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 A328602 seq(n)={my(v=sum(k=1, n, k*b(n, k, (i,j)->gcd(i,j)<>1))); vector(n, n, sumdiv(n, d, eulerphi(d)*v[n/d])/n)} \\ _Andrew Howroyd_, Oct 26 2019
%Y A328602 The non-necklace, non-circular version is A178470.
%Y A328602 The version for indivisibility (rather than co-primality) is A328600.
%Y A328602 The circularly coprime (as opposed to anti-coprime) version is A328597.
%Y A328602 Partitions with no consecutive parts relatively prime are A328187.
%Y A328602 Cf. A000031, A000740, A008965, A032153, A318728, A318729, A318748, A328172, A328188, A328220, A328335, A328336, A328601, A328609.
%K A328602 nonn
%O A328602 1,4
%A A328602 _Gus Wiseman_, Oct 25 2019
%E A328602 Terms a(26) and beyond from _Andrew Howroyd_, Oct 26 2019