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

0, 0, 0, 1, 2, 2, 2, 4, 9, 17, 30, 49, 76, 116, 180, 286, 460, 746, 1217, 1990, 3251, 5303, 8639, 14057, 22844, 37077, 60110, 97356, 157568, 254920, 412387, 667212, 1079754, 1747807, 2829756, 4582021, 7419619, 12014143, 19452288, 31492382, 50979547, 82517631

Offset

1,5

Links

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

Formula

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

a(n) ~ 1/(2*sqrt(5)) * ((1+sqrt(5))/2)^(n-1). - Vaclav Kotesovec, May 01 2014

Example

a(8) = 4: [2,2,2,2], [2,6], [4,4], [6,2].

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..50);

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, A199888, A201025.

Sequence in context: A160179 A021822 A153986 * A293177 A231382 A360314

Adjacent sequences: A199886 A199887 A199888 * A199890 A199891 A199892

Keyword

nonn

Author

Alois P. Heinz, Nov 11 2011

Status

approved