login
Number of partitions of n into nonprime parts.
(Formerly M0271 N0094)
47

%I M0271 N0094 #48 Oct 28 2023 11:24:32

%S 1,1,1,1,2,2,3,3,5,6,8,8,12,13,17,19,26,28,37,40,52,58,73,79,102,113,

%T 139,154,191,210,258,284,345,384,462,509,614,679,805,893,1060,1171,

%U 1382,1528,1792,1988,2319,2560,2986,3304,3823,4231,4888,5399,6219,6870

%N Number of partitions of n into nonprime parts.

%C Partial sums of A023895. - _Emeric Deutsch_, Apr 19 2006

%C Column k=0 of A222656. - _Alois P. Heinz_, May 29 2013

%D L. M. Chawla and S. A. Shad, On a trio-set of partition functions and their tables, J. Natural Sciences and Mathematics, 9 (1969), 87-96.

%D A. Murthy, Some new Smarandache sequences, functions and partitions, Smarandache Notions Journal Vol. 11 N. 1-2-3 Spring 2000 (but beware errors).

%D Amarnath Murthy and Charles Ashbacher, Generalized Partitions and Some New Ideas on Number Theory and Smarandache Sequences, Hexis, Phoenix; USA 2005. See Section 2.6.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Alois P. Heinz, <a href="/A002095/b002095.txt">Table of n, a(n) for n = 0..5000</a> (first 1001 terms from T. D. Noe)

%F G.f.: Product_{i>0} (1-x^prime(i))/(1-x^i). - _Vladeta Jovovic_, Jul 31 2004

%e a(6) = 3 from the partitions 6 = 1+1+1+1+1+1 = 4+1+1.

%p g:=product((1-x^ithprime(j))/(1-x^j),j=1..60): gser:=series(g,x=0,60): seq(coeff(gser,x,n),n=0..55); # _Emeric Deutsch_, Apr 19 2006

%t NonPrime[n_Integer] := FixedPoint[n + PrimePi[ # ] &, n + PrimePi[n]]; CoefficientList[ Series[1/Product[1 - x^NonPrime[i], {i, 1, 50}], {x, 0, 50}], x]

%o (Haskell)

%o a002095 = p a018252_list where

%o p _ 0 = 1

%o p ks'@(k:ks) m = if m < k then 0 else p ks' (m - k) + p ks m

%o -- _Reinhard Zumkeller_, Jan 15 2012

%o (PARI) first(n)=my(x='x+O('x^(n+1)),pr=1); forprime(p=2,n+1, pr *= (1-x^p)); pr/prod(i=1,n+1, 1-x^i) \\ _Charles R Greathouse IV_, Jun 23 2017

%Y Cf. A000607, A018252, A096258.

%K nonn,easy,nice

%O 0,5

%A _N. J. A. Sloane_

%E More terms from _James A. Sellers_, Dec 23 1999

%E Corrected by _Robert G. Wilson v_, Feb 11 2002