%I #9 Oct 27 2019 05:01:11

%S 0,0,0,0,1,0,2,1,2,5,4,7,6,13,14,20,30,38,50,68,97,132,176,253,328,

%T 470,631,901,1229,1709,2369,3269,4590,6383,8897,12428,17251,24229,

%U 33782,47404,66253,92859,130141,182468,256261,359675,505230,710058,997952,1404214

%N Number of necklace compositions of n with no part circularly followed by a divisor or a multiple.

%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="/A328601/b328601.txt">Table of n, a(n) for n = 1..200</a>

%F a(n) = A318730(n) - 1.

%e The a(5) = 1 through a(13) = 6 necklace compositions (empty column not shown):

%e (2,3) (2,5) (3,5) (2,7) (3,7) (2,9) (5,7) (4,9)

%e (3,4) (4,5) (4,6) (3,8) (2,3,7) (5,8)

%e (2,3,5) (4,7) (2,7,3) (6,7)

%e (2,5,3) (5,6) (3,4,5) (2,11)

%e (2,3,2,3) (3,5,4) (3,10)

%e (2,3,2,5) (2,3,5,3)

%e (2,3,4,3)

%t neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];

%t Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],neckQ[#]&&And@@Not/@Divisible@@@Partition[#,2,1,1]&&And@@Not/@Divisible@@@Reverse/@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)->i%j<>0 && j%i<>0))); vector(n, n, sumdiv(n, d, eulerphi(d)*v[n/d])/n)} \\ _Andrew Howroyd_, Oct 26 2019

%Y The non-necklace version is A328599.

%Y The case forbidding divisors only is A328600 or A318729 (with singletons).

%Y The non-necklace, non-circular version is A328508.

%Y The version for co-primality (instead of indivisibility) is A328597.

%Y Cf. A000740, A008965, A032153, A167606, A318748, A328171, A328460, A328593, A328598, A328602, A328603, A328608, A328609.

%K nonn

%O 1,7

%A _Gus Wiseman_, Oct 25 2019

%E Terms a(26) and beyond from _Andrew Howroyd_, Oct 26 2019