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

1, 1, 2, 3, 5, 8, 12, 21, 33, 57, 94, 167, 279, 491, 852, 1507, 2647, 4714, 8349, 14923, 26642, 47793, 85778, 154474, 278322, 502715, 908912, 1646205, 2984546, 5418652, 9847189, 17916000, 32625617, 59470539, 108493149, 198094482, 361965238, 661891579, 1211162270

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.

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

Sequence in context: A274376 A018149 A152909 * A118604 A261694 A287533

Adjacent sequences: A328594 A328595 A328596 * A328598 A328599 A328600

Keyword

nonn

Author

Gus Wiseman, Oct 23 2019

Extensions

Terms a(21) and beyond from Andrew Howroyd, Oct 26 2019

Status

approved