cp's OEIS Frontend

A328597 Number of necklace compositions of n where every pair of adjacent parts (including the last with the first) is relatively prime.

%I A328597 #13 Oct 27 2019 12:02:11
%S A328597 1,1,2,3,5,8,12,21,33,57,94,167,279,491,852,1507,2647,4714,8349,14923,
%T A328597 26642,47793,85778,154474,278322,502715,908912,1646205,2984546,
%U A328597 5418652,9847189,17916000,32625617,59470539,108493149,198094482,361965238,661891579,1211162270
%N A328597 Number of necklace compositions of n where every pair of adjacent parts (including the last with the first) is relatively prime.
%C A328597 A necklace composition of n is a finite sequence of positive integers summing to n that is lexicographically minimal among all of its cyclic rotations.
%H A328597 Andrew Howroyd, <a href="/A328597/b328597.txt">Table of n, a(n) for n = 1..200</a>
%F A328597 a(n > 1) = A318728(n) - 1.
%e A328597 The a(1) = 1 through a(7) = 12 necklace compositions:
%e A328597   (1)  (1,1)  (1,2)    (1,3)      (1,4)        (1,5)          (1,6)
%e A328597               (1,1,1)  (1,1,2)    (2,3)        (1,1,4)        (2,5)
%e A328597                        (1,1,1,1)  (1,1,3)      (1,2,3)        (3,4)
%e A328597                                   (1,1,1,2)    (1,3,2)        (1,1,5)
%e A328597                                   (1,1,1,1,1)  (1,1,1,3)      (1,1,1,4)
%e A328597                                                (1,2,1,2)      (1,1,2,3)
%e A328597                                                (1,1,1,1,2)    (1,1,3,2)
%e A328597                                                (1,1,1,1,1,1)  (1,2,1,3)
%e A328597                                                               (1,1,1,1,3)
%e A328597                                                               (1,1,2,1,2)
%e A328597                                                               (1,1,1,1,1,2)
%e A328597                                                               (1,1,1,1,1,1,1)
%t A328597 neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];
%t A328597 Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],neckQ[#]&&And@@CoprimeQ@@@Partition[#,2,1,1]&]],{n,10}]
%o A328597 (PARI)
%o A328597 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 A328597 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 A328597 The non-necklace version is A328609.
%Y A328597 The non-necklace non-circular version is A167606.
%Y A328597 The version with singletons is A318728.
%Y A328597 The aperiodic case is A318745.
%Y A328597 The indivisible (instead of coprime) version is A328600.
%Y A328597 The non-coprime (instead of coprime) version is A328602.
%Y A328597 Necklace compositions are A008965.
%Y A328597 Cf. A000031, A000740, A000837, A032153, A059966, A318729, A318748, A328172, A328598, A328599, A328601.
%K A328597 nonn
%O A328597 1,3
%A A328597 _Gus Wiseman_, Oct 23 2019
%E A328597 Terms a(21) and beyond from _Andrew Howroyd_, Oct 26 2019