Given $n$ I would like to find a lower bound (or a tight asymptotics) for the number $s(n)$ of solutions to $$ p_1 + \ldots + p_k \leq n \quad (1) $$ where $k$ is arbitrary and $p_1 \leq \ldots \leq p_k$ are odd prime numbers. I have edited the answer and gave three attempts I tried to use in order to find an asymptotics for $s(n)$ and the reason I failed to obtain an answer. I'll be thankful if someone can give further insights into the problem.

I have attempted to solve the problem in the following ways:

  1. By considering the set of primes $P$ in the interval $[2,\ldots,\sqrt{n}]$ whose size is at least $\frac{\sqrt{n}}{\log{n}}.$ We then analyze the number of combinations with repetition allowed from a set of $\frac{\sqrt{n}}{\log{n}}+1$ numbers where we pick $\sqrt{n}$ numbers. This estimate gives a worse bound than just considering the number of all partitions into odd primes of $n$. Is there any way to modify this reasoning in order to yield a better bound? Perhaps using another function instead of $\sqrt(n)?$

  2. If $p_p(n)$ denotes the number of partitions of $n$ into odd prime parts then we're basically tring to bound $\displaystyle \sum_{i=2}^n p_p(i).$ Since $p_p(i) \sim e^{C\sqrt{i/\log(i)}}$ for a constant $C$ one could use the integral bounding the summation to obtain a lower bound. Since $p_p(i)$ is not integrable one has to use a bound for it. The only reasonable bound I see is $ e^{\sqrt{i/log{i}}} > e^\sqrt[3]{i}$.Again, applying this bound, and considering the bound from the resulting integral we see that it is inferior to the one for the number of partitions of $n$ into odd primes. Is there any better bound for $p_p(i)$ or perhaps a superior way to analyze the integral?

  3. The generating function with the number of partitions of $n$ into prime as coefficients is $G(x) = \prod_{i\geq 1} \frac{1}{1-x^{p_i}}$ where $p_i$ is the $i$'th prime. So basically I am estimating the coefficients of the generating function that is obtained after applying the operation of convolution to $G(x).$ The book http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html contains a section entitled "saddle point method" related to the asymptotic estimate of coefficients for generating functions of that kind, but my knowledge of the related field is to scarce to really apply this method.

Anyone happens to see a superior solution to my problem?

  • $\begingroup$ I have voted to close as a duplicate of mathoverflow.net/questions/58408 $\endgroup$ Jul 9, 2011 at 19:18
  • $\begingroup$ Why is it a duplicate? In the linked question I've asked about the asymptotics of partitioning $n$ into $k$ parts. Here I am asking for the number of partitions $p_1 \leq \ldots \leq p_k$ such that $p_1 + \ldots + p_k \leq n$ how is this related? $\endgroup$
    – Jernej
    Jul 9, 2011 at 19:24
  • $\begingroup$ You might consider q_k(n), the number of umordered sums of primes >= k whose total is at most n. You should then find q_2(n) to be q_2(n-2) + q_3(n- 3) + q_5(n-5) plus not very many small order terms. Gerhard "Email Me About System Design" Paseman, 2011.07.09 $\endgroup$ Jul 9, 2011 at 19:44

2 Answers 2


If $T(n)$ denotes the number of partitions of $n$ into sums of primes, then

$T(n) = \exp{((\frac{2\pi}{\sqrt{3}}+o(1))\sqrt{\frac{n}{\log{n}}})}$.

See e.g. page 260 of the AMS-Chelsea edition of Ramanujan's collected papers.

  • $\begingroup$ Yeah, this was mentioned under point 2. too. I just didn't include the precise value of $C$ as it was irrelevant. $\endgroup$
    – Jernej
    Jul 21, 2011 at 15:39

The question has been answered on math.stackexchange, the answer here is just for the sake of completeness.

From https://math.stackexchange.com/questions/52737/estimating-an-integral we see that an asymptotically equivalent estimate is $2\sqrt{n\log{n}}\;e^{\sqrt{n/\log{n}}}.$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.