A111901 Number of partitions of n into parts that are primes or squares of primes.

1, 0, 1, 1, 2, 2, 3, 4, 5, 7, 8, 11, 13, 17, 20, 25, 30, 37, 44, 53, 63, 75, 89, 105, 123, 145, 169, 197, 229, 266, 307, 355, 408, 469, 538, 615, 703, 801, 912, 1035, 1175, 1330, 1504, 1698, 1914, 2155, 2423, 2721, 3051, 3418, 3824, 4273, 4770, 5319, 5925

Offset: 0

Author

Reinhard Zumkeller, Aug 20 2005

Keywords

• nonn

Examples

			G.f. = 1 + x^2 + x^3 + 2*x^4 + 2*x^5 + 3*x^6 + 4*x^7 + 5*x^8 + 7*x^9 + 8*x^10 + ...
a(10) = #{ 7+3, 5+5, 5+3+2, 2^2+2^2+2, 2^2+3+3, 2^2+2+2+2, 3+3+2+2, 2+2+2+2+2 } = 8.
		

Links

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

Crossrefs

Cf. A000607, A090677, A023893, A111902.

Programs

Maple

with(numtheory):
a:= proc(n) option remember; `if`(n=0, 1, add(a(n-j)*add(
     `if`(tau(d) in [2, 3], d, 0), d=divisors(j)), j=1..n)/n)
    end:
seq(a(n), n=0..60);  # Alois P. Heinz, Mar 30 2017

Mathematica

a[n_] := a[n] = If[n == 0, 1, Sum[a[n - j]*DivisorSum[j, If[2 <= DivisorSigma[0, #] <= 3, #, 0]&], {j, 1, n}]/n];
Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Apr 06 2017, after Alois P. Heinz *)

PARI

{a(n) = if(n < 0, 0, polcoeff( 1 / prod(k=1, primepi(n), (1 - x^prime(k)^2 + x*O(x^n)) * (1 - x^prime(k))), n))}; /* Michael Somos, Dec 26 2016 */

Formula

G.f.: Product_{k>=1} 1/((1 - x^prime(k))*(1 - x^(prime(k)^2))). - Ilya Gutkovskiy, Dec 26 2016