A235945 Number of partitions of n containing at least one prime.

0, 0, 1, 2, 3, 5, 8, 12, 17, 24, 34, 48, 65, 88, 118, 157, 205, 269, 348, 450, 575, 734, 929, 1176, 1473, 1845, 2297, 2856, 3527, 4355, 5346, 6558, 8004, 9759, 11848, 14374, 17363, 20958, 25210, 30292, 36278, 43412, 51792, 61733, 73383, 87146, 103239, 122194

Offset

0,4

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Formula

a(n) = A000041(n) - A002095(n).

Product_{k>0} 1/(1-x^k) - Product_{k>0} (1-x^prime(k))/(1-x^k). - Alois P. Heinz, Jan 18 2014

Example

a(5) = 5 because 5 partitions of 5 contain at least one prime: [5], [3,2], [3,1,1], [2,2,1], [2,1,1,1].

Maple

b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
       b(n, i-1)+`if`(i>n or isprime(i), 0, b(n-i, i))))
    end:
a:= n-> combinat[numbpart](n) -b(n, n):
seq(a(n), n=0..50);  # Alois P. Heinz, Jan 18 2014

Mathematica

b[n_, i_] := b[n, i] = If[n == 0, 1, If[i<1, 0, b[n, i-1] + If[i>n || PrimeQ[i], 0, b[n-i, i]]]]; a[n_] := PartitionsP[n]-b[n, n]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Jan 28 2014, after Alois P. Heinz *)

Crossrefs

Cf. A000041, A002095.

Sequence in context: A280276 A233969 A240202 * A129504 A241553 A241549

Adjacent sequences: A235942 A235943 A235944 * A235946 A235947 A235948

Keyword

nonn

Author

J. Stauduhar, Jan 17 2014

Status

approved