A199888 Number of compositions of n such that the number of parts and the smallest part are coprime.

1, 2, 4, 7, 14, 30, 62, 124, 247, 495, 994, 1999, 4020, 8076, 16204, 32482, 65076, 130326, 260927, 522298, 1045325, 2091849, 4185665, 8374551, 16754372, 33517355, 67048754, 134120372, 268277888, 536615992, 1073329437, 2146816436, 4293887542, 8588186785

Offset

1,2

Links

Alois P. Heinz, Table of n, a(n) for n = 1..500

Formula

a(n) = A000079(n-1) - A199889(n).

Example

a(4) = 7: [1,1,1,1], [1,1,2], [1,2,1], [1,3], [2,1,1], [3,1], [4].

Maple

b:= proc(n, t, g) option remember;
      `if`(n=0, `if`(igcd(g, t)=1, 1, 0),
       add(b(n-i, t+1, min(i, g)), i=1..n))
    end:
a:= n-> b(n, 0, infinity):
seq(a(n), n=1..40);

Mathematica

b[n_, t_, g_] := b[n, t, g] = If[n == 0, If[GCD[g, t] == 1, 1, 0], Sum[b[n-i, t+1, Min[i, g]], {i, 1, n}]]; a[n_] := b[n, 0, Infinity]; Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Nov 05 2014, after Alois P. Heinz *)

Crossrefs

Cf. A000079, A199889, A200928.

Sequence in context: A293336 A321401 A000671 * A157133 A367462 A202850

Adjacent sequences: A199885 A199886 A199887 * A199889 A199890 A199891

Keyword

nonn

Author

Alois P. Heinz, Nov 11 2011

Status

approved