Asymptotics for the number of ways to sum primes such that the sum is <= n - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T06:18:51Z http://mathoverflow.net/feeds/question/69900 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/69900/asymptotics-for-the-number-of-ways-to-sum-primes-such-that-the-sum-is-n Asymptotics for the number of ways to sum primes such that the sum is <= n Jernej 2011-07-09T19:03:55Z 2011-07-21T04:46:04Z <p>Hello!</p> <p>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.</p> <p>I have attempted to solve the problem in the following ways:</p> <ol> <li><p>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. <strong>This estimate gives a worse bound than just considering the number of all partitions into odd primes of $n$.</strong> Is there any way to modify this reasoning in order to yield a better bound? Perhaps using another function instead of $\sqrt(n)?$</p></li> <li><p>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}$.<strong>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.</strong> Is there any better bound for $p_p(i)$ or perhaps a superior way to analyze the integral?</p></li> <li><p>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 <a href="http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html" rel="nofollow">http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html</a> 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.</p></li> </ol> <p>Anyone happens to see a superior solution to my problem?</p> http://mathoverflow.net/questions/69900/asymptotics-for-the-number-of-ways-to-sum-primes-such-that-the-sum-is-n/70859#70859 Answer by Jernej for Asymptotics for the number of ways to sum primes such that the sum is <= n Jernej 2011-07-20T23:50:00Z 2011-07-20T23:50:00Z <p>The question has been answered on math.stackexchange, the answer here is just for the sake of completeness.</p> <p>From <a href="http://math.stackexchange.com/questions/52737/estimating-an-integral" rel="nofollow">http://math.stackexchange.com/questions/52737/estimating-an-integral</a> we see that an asymptotically equivalent estimate is $2\sqrt{n\log{n}}\;e^{\sqrt{n/\log{n}}}.$</p> http://mathoverflow.net/questions/69900/asymptotics-for-the-number-of-ways-to-sum-primes-such-that-the-sum-is-n/70875#70875 Answer by David Hansen for Asymptotics for the number of ways to sum primes such that the sum is <= n David Hansen 2011-07-21T04:46:04Z 2011-07-21T04:46:04Z <p>If $T(n)$ denotes the number of partitions of $n$ into sums of primes, then </p> <p>$T(n) = \exp{((\frac{2\pi}{\sqrt{3}}+o(1))\sqrt{\frac{n}{\log{n}}})}$. </p> <p>See e.g. page 260 of the AMS-Chelsea edition of Ramanujan's collected papers.</p>