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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000607 Number of partitions of n into prime parts.
(Formerly M0265 N0093)
111

%I M0265 N0093

%S 1,0,1,1,1,2,2,3,3,4,5,6,7,9,10,12,14,17,19,23,26,30,35,40,46,52,60,

%T 67,77,87,98,111,124,140,157,175,197,219,244,272,302,336,372,413,456,

%U 504,557,614,677,744,819,899,987,1083,1186,1298,1420,1552,1695,1850,2018,2198,2394,2605,2833,3079,3344

%N Number of partitions of n into prime parts.

%C a(n) gives the number of values of k such that A001414(k) = n. - _Howard A. Landman_, Sep 25 2001

%C Let W(n) = {prime p: There is at least one number m whose spf is p, and sopfr(m) = n}. Let V(n,p) = {m: sopfr(m) = n, p belongs to W(n)}. Then a(n) = sigma(|V(n,p)|). E.g.: W(10) = {2,3,5}, V(10,2) = {30,32,36}, V(10,3) = {21}, V(10,5) = {25}, so a(10) = 3+1+1 = 5. - _David James Sycamore_, Apr 14 2018

%D R. Ayoub, An Introduction to the Analytic Theory of Numbers, Amer. Math. Soc., 1963; see p. 203.

%D Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem, Mathematics and Computer Education, Vol. 31, No. 1, pp. 24-28, Winter 1997. MathEduc Database (Zentralblatt MATH, 1997c.01891).

%D B. C. Berndt and B. M. Wilson, Chapter 5 of Ramanujan's second notebook, pp. 49-78 of Analytic Number Theory (Philadelphia, 1980), Lect. Notes Math. 899, 1981, see Entry 29.

%D D. M. Burton, Elementary Number Theory, 5th ed., McGraw-Hill, 2002.

%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 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 T. D. Noe, Vaclav Kotesovec and H. Havermann, <a href="/A000607/b000607.txt">Table of n, a(n) for n = 0..50000</a> (first 1000 terms from T. D. Noe, terms 1001-20000 from Vaclav Kotesovec, terms 20001-50000 extracted from files by H. Havermann)

%H K. Alladi and P. Erdős, <a href="http://projecteuclid.org/euclid.pjm/1102811427">On an additive arithmetic function</a>, Pacific J. Math., Volume 71, Number 2 (1977), 275-294.

%H George E. Andrews, Arnold Knopfmacher, John Knopfmacher, <a href="http://dx.doi.org/10.1006/jnth.1999.2453">Engel expansions and the Rogers-Ramanujan identities</a> J. Number Theory 80 (2000), 273-290. See Eq. 2.1.

%H George E. Andrews, Arnold Knopfmacher, and Burkhard Zimmermann, <a href="http://dx.doi.org/10.1016/j.jnt.2005.08.012">On the Number of Distinct Multinomial Coefficients</a>, Journal of Number Theory, Volume 118, Issue 1, May 2006, Pages 15-30.

%H Mohammad K. Azarian, <a href="http://www.math-cs.ucmo.edu/~mjms/2004.1/azar6.pdf">A Generalization of the Climbing Stairs Problem II</a>, Missouri Journal of Mathematical Sciences, Vol. 16, No. 1, Winter 2004, pp. 12-17. Zentralblatt MATH, Zbl 1071.05501.

%H Paul Barry, <a href="https://arxiv.org/abs/1803.06408">Three Études on a sequence transformation pipeline</a>, arXiv:1803.06408 [math.CO], 2018.

%H Johann Bartel, R. K. Bhaduri, Matthias Brack, and M. V. N. Murthy, <a href="https://doi.org/10.1103/PhysRevE.95.052108">Asymptotic prime partitions of integers</a>, Phys. Rev. E, 95 (2017), 052108, <a href="https://arxiv.org/abs/1609.06497">arXiv:1609.06497 [math-ph]</a>.

%H Edward A. Bender, <a href="http://www.jstor.org/stable/2028691">Asymptotic methods in enumeration</a>, SIAM Review 16 (1974), no. 4, p. 509.

%H L. M. Chawla and S. A. Shad, <a href="http://www.jstor.org/stable/2004512">Review of "On a trio-set of partition functions and their tables"</a>, Mathematics of Computation, Vol. 24, No. 110 (Apr., 1970), pp. 490-491.

%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see Section VIII.6, pp. 576ff.

%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.

%H O. P. Gupta and S. Luthra, <a href="http://www.new.dli.ernet.in/rawdataupload/upload/insa/INSA_2/20005ad0_181.pdf">Partitions into primes</a>, Proc. Nat. Inst. Sci. India. Part A. 21 (1955), 181-184.

%H R. K. Guy, <a href="/A000081/a000081.pdf">Letter to N. J. A. Sloane, 1988-04-12</a> (annotated scanned copy)

%H R. K. Guy, <a href="http://www.jstor.org/stable/2322249">The strong law of small numbers</a>. Amer. Math. Monthly 95 (1988), no. 8, 697-712.

%H R. K. Guy, <a href="/A005165/a005165.pdf">The strong law of small numbers</a>. Amer. Math. Monthly 95 (1988), no. 8, 697-712. [Annotated scanned copy]

%H H. Havermann, <a href="http://chesswanks.com/seq/sopfr/">Tables of sum-of-prime-factors sequences (including sequence lengths, i.e. number of prime-parts partitions, for the first 50000).</a>

%H Vaclav Kotesovec, <a href="/A000607/a000607_2.jpg">Graph - asymptotic ratio for log(a(n)), without minor asymptotic term</a>

%H Vaclav Kotesovec, <a href="http://mathoverflow.net/questions/180858/wrong-asymptotics-of-oeis-a000607">Wrong asymptotics of OEIS A000607?</a> (MathOverflow). Includes discussion of the contradiction between the results for the next-to-leading term in the asymptotic formulas by Vaughan and by Bartel et al.

%H John F. Loase (splurge(AT)aol.com), David Lansing, Cassie Hryczaniuk and Jamie Cahoon, <a href="http://www.maa.org/programs/faculty-and-departments/classroom-capsules-and-notes/a-variant-of-the-partition-function">A Variant of the Partition Function</a>, College Mathematics Journal, Vol. 36, No. 4 (Sep 2005), pp. 320-321.

%H Ljuben Mutafchiev, <a href="http://arxiv.org/abs/1407.4688">A Note on Goldbach Partitions of Large Even Integers</a>, arXiv:1407.4688 [math.NT], 2014-2015.

%H Igor Pak, <a href="https://arxiv.org/abs/1803.06636">Complexity problems in enumerative combinatorics</a>, arXiv:1803.06636 [math.CO], 2018.

%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>

%H R. C. Vaughan, <a href="http://dx.doi.org/10.1007/s11139-007-9037-5">On the number of partitions into primes</a>, Ramanujan J. vol. 15, no. 1 (2008) 109-121.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PrimePartition.html">Prime Partition.</a>

%H Roger Woodford, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL10/Woodford/woodford82.html">Bounds for the Eventual Positivity of Difference Functions of Partitions</a>, Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.3.

%H <a href="/index/Go#Goldbach">Index entries for sequences related to Goldbach conjecture</a>

%F Asymptotically a(n) ~ exp(2 Pi sqrt(n/log n) / sqrt(3)) (Ayoub).

%F a(n) = (1/n)*Sum_{k=1..n} A008472(k)*a(n-k). - _Vladeta Jovovic_, Aug 27 2002

%F G.f.: 1/Product_{k>=1}(1-x^prime(k)).

%F See the partition arrays A116864 and A116865.

%F From _Vaclav Kotesovec_, Sep 15 2014 [Corrected by _Andrey Zabolotskiy_, May 26 2017]: (Start)

%F It is surprising that the ratio of the formula for log(a(n)) to the approximation 2 * Pi * sqrt(n/(3*log(n))) exceeds 1. For n=20000 the ratio is 1.00953, and for n=50000 (using the value from Havermann's tables) the ratio is 1.02458, so the ratio is increasing. See graph above.

%F A more refined asymptotic formula is found by Vaughan in Ramanujan J. 15 (2008), p. 109-121, and corrected by Bartel et al (2017): log(a(n)) = 2*Pi*sqrt(n/(3*log(n))) * (1 - log(log(n))/(2*log(n)) + O(1/log(n)))

%F See Bartel, Bhaduri, Brack, Murthy (2017) for a more complete asymptotic expansion. (End)

%F G.f.: 1 + Sum_{i>=1} x^prime(i) / Product_{j=1..i} (1 - x^prime(j)). - _Ilya Gutkovskiy_, May 07 2017

%e n = 10 has a(10) = 5 partitions into prime parts: 10 = 2 + 2 + 2 + 2 + 2 = 2 + 2 + 3 + 3 = 2 + 3 + 5 = 3 + 7 = 5 + 5.

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

%p with(gfun):

%p t1:=mul(1/(1-q^ithprime(n)),n=1..51):

%p t2:=series(t1,q,50):

%p t3:=seriestolist(t2);

%t CoefficientList[ Series[1/Product[1 - x^Prime[i], {i, 1, 50}], {x, 0, 50}], x]

%t f[n_] := Length@ IntegerPartitions[n, All, Prime@ Range@ PrimePi@ n]; Array[f, 57] (* _Robert G. Wilson v_, Jul 23 2010 *)

%t Table[Length[Select[IntegerPartitions[n],And@@PrimeQ/@#&]],{n,0,60}] (* _Harvey P. Dale_, Apr 22 2012 *)

%t Comment from Thomas Vogler, Dec 10 2015 (Start): The following code uses the Euler transform. The code caches already computed values and is faster than using the built-in IntegerPartitions[] function.

%t a[n_] := a[n] = If[PrimeQ[n], 1, 0];

%t c[n_] := c[n] = Plus @@ Map[# a[#] &, Divisors[n]];

%t b[n_] := b[n] = (c[n] + Sum[c[k] b[n - k], {k, 1, n - 1}])/n;

%t Table[b[n], {n, 1, 20}] (End)

%o (PARI) N=66;x='x+O('x^N); Vec(1/prod(k=1,N,1-x^prime(k))) \\ _Joerg Arndt_, Sep 04 2014

%o (Haskell)

%o a000607 = p a000040_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_, Aug 05 2012

%o (Sage) [Partitions(n, parts_in=(prime_range(n+1))).cardinality() for n in range(1000)] # _Giuseppe Coppoletta_, Jul 11 2016

%o (Python)

%o from sympy import primefactors

%o l=[1, 0]

%o for n in xrange(2, 101):l+=[sum([sum(primefactors(k))*l[n - k] for k in xrange(1, n + 1)])/n, ]

%o print l # _Indranil Ghosh_, Jul 13 2017

%Y G.f. = 1 / g.f. for A046675. See A046113 for the ordered (compositions) version.

%Y Cf. A046676, A048165, A004526, A051034, A000040, A001414, A000586, A000041, A070214, A192541, A112021, A056768, A128515, A000586, A319265, A319266.

%Y Row sums of array A116865 and of triangle A261013.

%K easy,nonn,nice,changed

%O 0,6

%A _N. J. A. Sloane_

%E Maple program fixed by _Vaclav Kotesovec_, Sep 14 2014

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 September 19 03:05 EDT 2018. Contains 315155 sequences. (Running on oeis4.)