login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000586 Number of partitions of n into distinct primes.
(Formerly M0022 N0004 N0039)
44

%I M0022 N0004 N0039

%S 1,0,1,1,0,2,0,2,1,1,2,1,2,2,2,2,3,2,4,3,4,4,4,5,5,5,6,5,6,7,6,9,7,9,

%T 9,9,11,11,11,13,12,14,15,15,17,16,18,19,20,21,23,22,25,26,27,30,29,

%U 32,32,35,37,39,40,42,44,45,50,50,53,55,57,61,64,67,70,71,76,78,83,87,89,93,96

%N Number of partitions of n into distinct primes.

%D H. Gupta, Certain averages connected with partitions. Res. Bull. Panjab Univ. no. 124 1957 427-430.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence in two entries, N0004 and N0039).

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

%H T. D. Noe, <a href="/A000586/b000586.txt">Table of n, a(n) for n = 0..1000</a>

%H Edray Herber Goins and Talitha M. Washington, <a href="https://arxiv.org/abs/0909.5459">On the generalized climbing stairs problem</a>, Ars Combin. 117 (2014), 183-190. MR3243840 (Reviewed), arXiv:0909.5459 [math.CO].

%H H. Gupta, <a href="http://www.dli.gov.in/rawdataupload/upload/insa/INSA_2/20005ad0_185.pdf">Partitions into distinct primes</a>, Proc. Nat. Acad. Sci. India, 21 (1955), 185-187.

%F G.f.: Product_{k=1..inf} (1+x^prime(k)).

%F a(n) = A184171(n) + A184172(n). - _R. J. Mathar_, Jan 10 2011

%F a(n) = Sum_{k=0..A024936(n)} A219180(n,k). - _Alois P. Heinz_, Nov 13 2012

%e n=16 has a(16) = 3 partitions into distinct prime parts: 16 = 2+3+11 = 3+13 = 5+11.

%p b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,

%p b(n, i-1)+`if`(ithprime(i)>n, 0, b(n-ithprime(i), i-1))))

%p end:

%p a:= n-> b(n, numtheory[pi](n)):

%p seq(a(n), n=0..100); # _Alois P. Heinz_, Nov 15 2012

%t CoefficientList[Series[Product[(1+x^Prime[k]), {k, 24}], {x, 0, Prime[24]}], x]

%t b[n_, i_] := b[n, i] = If[n == 0, 1, If[i < 1, 0, b[n, i-1] + If[Prime[i] > n, 0, b[n - Prime[i], i-1]]]]; a[n_] := b[n, PrimePi[n]]; Table[a[n], {n, 0, 100}] (* _Jean-Fran├žois Alcover_, Apr 09 2014, after _Alois P. Heinz_ *)

%o (Haskell)

%o a000586 = p a000040_list where

%o p _ 0 = 1

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

%o -- _Reinhard Zumkeller_, Aug 05 2012

%o (PARI) a(n,k=n)=if(n<1, !n, my(s);forprime(p=2,k,s+=a(n-p,p-1));s) \\ _Charles R Greathouse IV_, Nov 20 2012

%Y Cf. A000041, A070215, A000607, A112022, A000607, A000009.

%K nonn,nice,easy

%O 0,6

%A _N. J. A. Sloane_. Entry revised by _N. J. A. Sloane_, Jun 10 2012

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified June 24 07:19 EDT 2017. Contains 288697 sequences.