|
%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
|
