OFFSET
1,3
COMMENTS
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.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..200
FORMULA
a(n > 1) = A318728(n) - 1.
EXAMPLE
The a(1) = 1 through a(7) = 12 necklace compositions:
(1) (1,1) (1,2) (1,3) (1,4) (1,5) (1,6)
(1,1,1) (1,1,2) (2,3) (1,1,4) (2,5)
(1,1,1,1) (1,1,3) (1,2,3) (3,4)
(1,1,1,2) (1,3,2) (1,1,5)
(1,1,1,1,1) (1,1,1,3) (1,1,1,4)
(1,2,1,2) (1,1,2,3)
(1,1,1,1,2) (1,1,3,2)
(1,1,1,1,1,1) (1,2,1,3)
(1,1,1,1,3)
(1,1,2,1,2)
(1,1,1,1,1,2)
(1,1,1,1,1,1,1)
MATHEMATICA
neckQ[q_]:=Array[OrderedQ[{q, RotateRight[q, #]}]&, Length[q]-1, 1, And];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], neckQ[#]&&And@@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 version is A328609.
The non-necklace non-circular version is A167606.
The version with singletons is A318728.
The aperiodic case is A318745.
The indivisible (instead of coprime) version is A328600.
The non-coprime (instead of coprime) version is A328602.
Necklace compositions are A008965.
KEYWORD
nonn
AUTHOR
Gus Wiseman, Oct 23 2019
EXTENSIONS
Terms a(21) and beyond from Andrew Howroyd, Oct 26 2019
STATUS
approved