OFFSET
1,4
COMMENTS
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.
Circularity means the last part is followed by the first.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..200
EXAMPLE
The a(2) = 1 through a(10) = 8 necklace compositions:
(2) (3) (4) (5) (6) (7) (8) (9) (10)
(2,2) (2,4) (2,6) (3,6) (2,8)
(3,3) (4,4) (3,3,3) (4,6)
(2,2,2) (2,2,4) (5,5)
(2,2,2,2) (2,2,6)
(2,4,4)
(2,2,2,4)
(2,2,2,2,2)
The a(19) = 3 necklace compositions are: (19), (3,6,4,6), (2,2,6,3,6).
MATHEMATICA
neckQ[q_]:=Array[OrderedQ[{q, RotateRight[q, #]}]&, Length[q]-1, 1, And];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], neckQ[#]&&And@@Not/@CoprimeQ@@@Partition[#, 2, 1, 1]&]], {n, 10}]
PROG
(PARI)
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, ]}
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
CROSSREFS
The non-necklace, non-circular version is A178470.
The version for indivisibility (rather than co-primality) is A328600.
The circularly coprime (as opposed to anti-coprime) version is A328597.
Partitions with no consecutive parts relatively prime are A328187.
KEYWORD
nonn
AUTHOR
Gus Wiseman, Oct 25 2019
EXTENSIONS
Terms a(26) and beyond from Andrew Howroyd, Oct 26 2019
STATUS
approved