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