A328597 - OEIS

%I #13 Oct 27 2019 12:02:11

%S 1,1,2,3,5,8,12,21,33,57,94,167,279,491,852,1507,2647,4714,8349,14923,

%T 26642,47793,85778,154474,278322,502715,908912,1646205,2984546,

%U 5418652,9847189,17916000,32625617,59470539,108493149,198094482,361965238,661891579,1211162270

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

%C 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 Andrew Howroyd, <a href="/A328597/b328597.txt">Table of n, a(n) for n = 1..200</a>

%F a(n > 1) = A318728(n) - 1.

%e The a(1) = 1 through a(7) = 12 necklace compositions:

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

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

%e                        (1,1,1,1)  (1,1,3)      (1,2,3)        (3,4)

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

%e                                   (1,1,1,1,1)  (1,1,1,3)      (1,1,1,4)

%e                                                (1,2,1,2)      (1,1,2,3)

%e                                                (1,1,1,1,2)    (1,1,3,2)

%e                                                (1,1,1,1,1,1)  (1,2,1,3)

%e                                                               (1,1,1,1,3)

%e                                                               (1,1,2,1,2)

%e                                                               (1,1,1,1,1,2)

%e                                                               (1,1,1,1,1,1,1)

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

%t Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],neckQ[#]&&And@@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 version is A328609.

%Y The non-necklace non-circular version is A167606.

%Y The version with singletons is A318728.

%Y The aperiodic case is A318745.

%Y The indivisible (instead of coprime) version is A328600.

%Y The non-coprime (instead of coprime) version is A328602.

%Y Necklace compositions are A008965.

%Y Cf. A000031, A000740, A000837, A032153, A059966, A318729, A318748, A328172, A328598, A328599, A328601.

%K nonn

%O 1,3

%A _Gus Wiseman_, Oct 23 2019

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