A318729 Number of cyclic compositions (necklaces of positive integers) summing to n that have only one part or whose consecutive parts (including the last with first) are indivisible.

1, 1, 1, 1, 2, 1, 3, 2, 4, 6, 6, 8, 11, 19, 21, 30, 41, 59, 79, 112, 157, 219, 305, 430, 605, 860, 1210, 1727, 2424, 3463, 4905, 7001, 9954, 14211, 20271, 28980, 41392, 59254, 84800, 121540, 174163, 249932, 358578, 515091, 739933, 1063827, 1529767, 2201383

Offset

1,5

Links

Andrew Howroyd, Table of n, a(n) for n = 1..100

Formula

a(n) = A328600(n) + 1. - Andrew Howroyd, Oct 27 2019

Example

The a(13) = 11 cyclic compositions with successive parts indivisible:
  (13)
  (2,11) (3,10) (4,9) (5,8) (6,7)
  (2,4,7) (2,6,5) (2,8,3) (3,6,4)
  (2,3,5,3)

Mathematica

neckQ[q_]:=Array[OrderedQ[{q, RotateRight[q, #]}]&, Length[q]-1, 1, And];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], Or[Length[#]==1, neckQ[#]&&And@@Not/@Divisible@@@Partition[#, 2, 1, 1]]&]], {n, 20}]

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)->i%j<>0))); vector(n, n, 1 + sumdiv(n, d, eulerphi(d)*v[n/d])/n)} \\ Andrew Howroyd, Oct 27 2019

Crossrefs

Cf. A000740, A008965, A059966, A167606, A285573, A303362, A304713, A316476, A318726, A318727, A318728, A318730, A328600.

Sequence in context: A117194 A340647 A318746 * A024467 A215489 A182167

Adjacent sequences: A318726 A318727 A318728 * A318730 A318731 A318732

Keyword

nonn

Author

Gus Wiseman, Sep 02 2018

Extensions

Terms a(21) and beyond from Andrew Howroyd, Sep 08 2018

Name corrected by Gus Wiseman, Nov 04 2019

Status

approved