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

Author

Gus Wiseman, Sep 02 2018

Keywords

• nonn

Examples

			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)
		

Links

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

Crossrefs

Cf. A000740, A008965, A059966, A167606, A285573, A303362, A304713, A316476, A318726, A318727, A318728, A318729, A328601.

Programs

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}]

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

Formula

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

Extensions

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