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,5

Links

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

Formula

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

Example

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.

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

Prog

(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 */

Crossrefs

Cf. A000607, A090677, A023893, A111902.

Sequence in context: A112192 A017841 A304329 * A316202 A326671 A134727

Adjacent sequences: A111898 A111899 A111900 * A111902 A111903 A111904

Keyword

nonn

Author

Reinhard Zumkeller, Aug 20 2005

Status

approved