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

1, 2, 3, 4, 6, 9, 13, 22, 34, 58, 95, 168, 280, 492, 853, 1508, 2648, 4715, 8350, 14924, 26643, 47794, 85779, 154475, 278323, 502716, 908913, 1646206, 2984547, 5418653, 9847190, 17916001, 32625618, 59470540, 108493150, 198094483, 361965239, 661891580, 1211162271

Offset

1,2

Links

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

Formula

a(n) = A328597(n) + 1 for n > 1. - Andrew Howroyd, Oct 27 2019

Example

The a(7) = 13 cyclic compositions with adjacent parts coprime:
  7,
  16, 25, 34,
  115,
  1114, 1213, 1132, 1123,
  11113, 11212,
  111112,
  1111111.

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

Crossrefs

Cf. A000740, A000837, A008965, A059966, A100953, A167606, A296302, A318726, A318727, A328597.

Sequence in context: A022860 A022859 A352039 * A220126 A328071 A039884

Adjacent sequences: A318725 A318726 A318727 * A318729 A318730 A318731

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