show/hide this revision's text 3 added 16 characters in body

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.$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?
show/hide this revision's text 2 added further insights into what I have tried in order to solve the problem

Given $n$ I would like to find a lower bound $s(n)$ (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. There are two ways I have edited the answer and gave three attempts I tried to use in which order to find an asymptotics for $s(n)$ and the reason I think a solution could failed to obtain an answer. I'll be obtainedthankful if someone can give further insights into the problem.

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

  • By considering the set of primes $P$ in the interval $[2,\ldots,\sqrt{n}]$ whose size is at least $\frac{\sqrt{n}}{\log{n}}$ (according to wikipedia this should hold for large enough $n$). \frac{\sqrt{n}}{\log{n}}.$ We then analyze the number of ways of choosing (combinations with order and repetition allowed ) $\sqrt{n}$ objects from $P\cup {0}$ (zero means no choice).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)?$

  • 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).$ 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.

    • Both ways have their technicalities Since $p_p(i)$ is not integrable one has to consider (in the first oneuse a bound for it. The only reasonable bound I see is $ e^{\sqrt{i/log{i}}} > e^\sqrt[3]{i}$.Again, what kind of subset to pick in order applying this bound, and considering the bound from the resulting integral we see that it is inferior to get the maximal one for the number of partitions ) of $n.$ Is there any better bound for $p_p(i)$ or in the second one, how perhaps a superior way to deal analyze the integral?

  • The generating function with the fact that number of partitions of $f(i) = e^{C\sqrt{i/\log(i)}}$ n$ into prime as coefficients is just an asymptotics for $p_p$ and how to optimaly bound G(x) = \prod_{i\geq 1} \frac{1}{1-x^{p_i}}$ where $f$ as it p_i$ is not integrable?the $i$'th prime. So basically I somehow think there 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 nicer way section entitled "saddle point method" related to solve the problem (obtanining a better bound) or asymptotic estimate of coefficients for generating functions of that perhaps an answer kind, but my knowledge of the related field is already knownto scarce to really apply this method.I would thus like

    • Anyone happens to hear if anyone has see a nicer way superior solution to actually solve this my problemor perhaps knows the right asymptotics for it.?
    show/hide this revision's text 1

    Asymptotics for the number of ways to sum primes such that the sum is <= n

    Hello!

    Given $n$ I would like to find a lower bound $s(n)$ (or a tight asymptotics) for the number 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 prime numbers. There are two ways in which I think a solution could be obtained:

    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}}$ (according to wikipedia this should hold for large enough $n$). We then analyze the number of ways of choosing (with order and repetition allowed) $\sqrt{n}$ objects from $P\cup {0}$ (zero means no choice). $$ $$

    2. If $p_p(n)$ denotes the number of partitions of $n$ into 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.

    Both ways have their technicalities one has to consider (in the first one, what kind of subset to pick in order to get the maximal number of partitions) or in the second one, how to deal with the fact that $f(i) = e^{C\sqrt{i/\log(i)}}$ is just an asymptotics for $p_p$ and how to optimaly bound $f$ as it is not integrable?

    I somehow think there is a nicer way to solve the problem (obtanining a better bound) or that perhaps an answer is already known. I would thus like to hear if anyone has a nicer way to actually solve this problem or perhaps knows the right asymptotics for it.