A318730 Number of cyclic compositions (necklaces of positive integers) summing to n with adjacent parts (including the last and first part) being indivisible (either way).

1, 1, 1, 1, 2, 1, 3, 2, 3, 6, 5, 8, 7, 14, 15, 21, 31, 39, 51, 69, 98, 133, 177, 254, 329, 471, 632, 902, 1230, 1710, 2370, 3270, 4591, 6384, 8898, 12429, 17252, 24230, 33783, 47405, 66254, 92860, 130142, 182469, 256262, 359676, 505231, 710059, 997953, 1404215

Offset

1,5

Links

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

Formula

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

Example

The a(14) = 14 cyclic compositions with adjacent parts indivisible either way:
  (14)
  (3,11) (4,10) (5,9) (6,8)
  (2,5,7) (2,7,5) (3,4,7) (3,7,4)
  (2,3,2,7) (2,3,4,5) (2,5,2,5) (2,5,4,3) (3,4,3,4)

Mathematica

neckQ[q_]:=Array[OrderedQ[{q, RotateRight[q, #]}]&, Length[q]-1, 1, And];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], Or[Length[#]==1, And[neckQ[#], And@@Not/@Divisible@@@Partition[#, 2, 1, 1], And@@Not/@Divisible@@@Reverse/@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 && j%i<>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, A318729, A328601.

Sequence in context: A318747 A297367 A118010 * A259974 A243561 A135550

Adjacent sequences: A318727 A318728 A318729 * A318731 A318732 A318733

Keyword

nonn

Author

Gus Wiseman, Sep 02 2018

Extensions

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

Status

approved