Hello!


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?



Asymptotics for the number of ways to sum primes such that the sum is <= n
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}}}.$


