A023895 Number of partitions of n into composite parts.

1, 0, 0, 0, 1, 0, 1, 0, 2, 1, 2, 0, 4, 1, 4, 2, 7, 2, 9, 3, 12, 6, 15, 6, 23, 11, 26, 15, 37, 19, 48, 26, 61, 39, 78, 47, 105, 65, 126, 88, 167, 111, 211, 146, 264, 196, 331, 241, 426, 318, 519, 408, 657, 511, 820, 651, 1010, 833, 1252, 1028, 1564, 1301, 1900

Offset

0,9

Comments

First differences of A002095. - Emeric Deutsch, Apr 03 2006

a(n+1) > a(n) for n > 108. - Reinhard Zumkeller, Aug 22 2007

Links

Alois P. Heinz, Table of n, a(n) for n = 0..5000 (terms n = 0..150 from Reinhard Zumkeller)

Formula

G.f.: (1-x)*Product_{j>=1} (1-x^prime(j))/(1-x^j). - Emeric Deutsch, Apr 03 2006

Example

a(12) = 4 because 12 = 4 + 4 + 4 = 6 + 6 = 4 + 8 = 12 (itself a composite number).

Maple

g:=(1-x)*product((1-x^ithprime(j))/(1-x^j), j=1..80): gser:=series(g, x=0, 70): seq(coeff(gser, x, n), n=0..62); # Emeric Deutsch, Apr 03 2006
# second Maple program:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<2, 0,
       b(n, i-1)+ `if`(i>n or isprime(i), 0, b(n-i, i))))
    end:
a:= n-> b(n$2):
seq(a(n), n=0..70);  # Alois P. Heinz, May 29 2013

Mathematica

Composite[n_Integer] := FixedPoint[n + PrimePi[ # ] + 1 &, n + PrimePi[n] + 1]; CoefficientList[ Series[1/Product[1 - x^Composite[i], {i, 1, 50}], {x, 0, 75}], x]
(* Second program: *)
b[n_, i_] := b[n, i] = If[n==0, 1, If[i<2, 0, b[n, i-1] + If[i>n || PrimeQ[i], 0, b[n-i, i]]]]; a[n_] := b[n, n]; Table[a[n], {n, 0, 70}] (* Jean-François Alcover, Feb 16 2017, after Alois P. Heinz *)

Prog

(Haskell)
a023895 = p a002808_list where
   p _          0 = 1
   p ks'@(k:ks) m = if m < k then 0 else p ks' (m - k) + p ks m
-- Reinhard Zumkeller, Jan 15 2012

Crossrefs

Cf. A002808.

Cf. A002095.

Cf. A132456.

Cf. A204389.

Sequence in context: A229817 A080966 A187150 * A070963 A174064 A139158

Adjacent sequences: A023892 A023893 A023894 * A023896 A023897 A023898

Keyword

nonn

Author

Olivier Gérard

Extensions

More terms from Reinhard Zumkeller, Aug 22 2007

Status

approved