cp's OEIS Frontend

A023895 Number of partitions of n into composite parts.

%I A023895 #31 Nov 03 2023 11:08:17
%S A023895 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,
%T A023895 48,26,61,39,78,47,105,65,126,88,167,111,211,146,264,196,331,241,426,
%U A023895 318,519,408,657,511,820,651,1010,833,1252,1028,1564,1301,1900
%N A023895 Number of partitions of n into composite parts.
%C A023895 First differences of A002095. - _Emeric Deutsch_, Apr 03 2006
%C A023895 a(n+1) > a(n) for n > 108. - _Reinhard Zumkeller_, Aug 22 2007
%H A023895 Alois P. Heinz, <a href="/A023895/b023895.txt">Table of n, a(n) for n = 0..5000</a> (terms n = 0..150 from Reinhard Zumkeller)
%F A023895 G.f.: (1-x)*Product_{j>=1} (1-x^prime(j))/(1-x^j). - _Emeric Deutsch_, Apr 03 2006
%e A023895 a(12) = 4 because 12 = 4 + 4 + 4 = 6 + 6 = 4 + 8 = 12 (itself a composite number).
%p A023895 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
%p A023895 # second Maple program:
%p A023895 b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<2, 0,
%p A023895        b(n, i-1)+ `if`(i>n or isprime(i), 0, b(n-i, i))))
%p A023895     end:
%p A023895 a:= n-> b(n$2):
%p A023895 seq(a(n), n=0..70);  # _Alois P. Heinz_, May 29 2013
%t A023895 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]
%t A023895 (* Second program: *)
%t A023895 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_ *)
%o A023895 (Haskell)
%o A023895 a023895 = p a002808_list where
%o A023895    p _          0 = 1
%o A023895    p ks'@(k:ks) m = if m < k then 0 else p ks' (m - k) + p ks m
%o A023895 -- _Reinhard Zumkeller_, Jan 15 2012
%Y A023895 Cf. A002808.
%Y A023895 Cf. A002095.
%Y A023895 Cf. A132456.
%Y A023895 Cf. A204389.
%K A023895 nonn
%O A023895 0,9
%A A023895 _Olivier Gérard_
%E A023895 More terms from _Reinhard Zumkeller_, Aug 22 2007