login
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).
5
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
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
KEYWORD
nonn
AUTHOR
Gus Wiseman, Sep 02 2018
EXTENSIONS
Terms a(21) and beyond from Andrew Howroyd, Sep 08 2018
STATUS
approved