Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.


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?

share|improve this question
I have voted to close as a duplicate of mathoverflow.net/questions/58408 –  Bruce Westbury Jul 9 '11 at 19:18
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? –  Jernej Jul 9 '11 at 19:24
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 –  Gerhard Paseman Jul 9 '11 at 19:44

2 Answers 2

up vote 2 down vote accepted

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

From http://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}}}.$

share|improve this answer

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.

share|improve this answer
Yeah, this was mentioned under point 2. too. I just didn't include the precise value of $C$ as it was irrelevant. –  Jernej Jul 21 '11 at 15:39

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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