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

Author

J. Stauduhar, Jan 17 2014

Keywords

• nonn

Examples

			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].
		

Links

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

Crossrefs

Cf. A000041, A002095.

Programs

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 *)

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