A318748 Number of integer compositions of n that have only one part or whose consecutive parts are coprime and the last and first part are also coprime.

1, 1, 2, 4, 7, 13, 24, 43, 82, 151, 285, 535, 1005, 1883, 3533, 6631, 12460, 23407, 43952, 82538, 154999, 291088, 546674, 1026687, 1928118, 3621017, 6800300, 12771086, 23984329, 45042959, 84591339, 158863807, 298348613, 560303342, 1052258402, 1976157510

Offset

0,3

Links

Andrew Howroyd, Table of n, a(n) for n = 0..200

Formula

a(n) = A328609(n) + 1 for n > 1. - Andrew Howroyd, Nov 01 2019

Example

The a(5) = 13 compositions with adjacent parts coprime:
  (5)
  (41) (14) (32) (23)
  (311) (131) (113)
  (2111) (1211) (1121) (1112)
  (11111)
Missing from this list are (221), (212), and (122).

Mathematica

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], Or[Length[#]==1, 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)={concat([1], vector(n, i, i > 1) + sum(k=1, n, b(n, k, (i, j)->gcd(i, j)==1)))} \\ Andrew Howroyd, Nov 01 2019

Crossrefs

Cf. A000740, A008965, A059966, A100953, A167606, A296302, A318726, A318727, A318728, A318745, A328609.

Sequence in context: A049285 A002843 A128742 * A107281 A006744 A054175

Adjacent sequences: A318745 A318746 A318747 * A318749 A318750 A318751

Keyword

nonn

Author

Gus Wiseman, Sep 02 2018

Extensions

a(21)-a(35) from Alois P. Heinz, Sep 02 2018

Name corrected by Gus Wiseman, Nov 04 2019

Status

approved