Upper bounds for the sum of primes <= n - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T01:51:50Z http://mathoverflow.net/feeds/question/63412 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/63412/upper-bounds-for-the-sum-of-primes-n Upper bounds for the sum of primes <= n Jernej 2011-04-29T13:50:26Z 2013-04-26T12:54:20Z <p>Let $s(n)$ denote the sum of primes less than or equal to n. Clearly, $s(n)$ is bounded from above by the sum of the first $n/2$ odd integers $+1$. $s(n)$ is also bounded by the sum of the first $n$ primes, which is asymptotically equivalent to $\frac{n^2}{2\log{n}}$. It should thus be possible to find estimates for $s(n)$ using the fact that for an $\epsilon > 0$ and $n$ large enough $s(n) &lt; (1+\epsilon)\frac{n^2}{\log{n}}.$</p> <p>I would like to know if there are any known sharp upper bounds for $s(n)$. That is, I am looking for a function $f(n)$ such that for every $n > N_0$ $$s(n) \leq f(n)$$</p> <p>As a way of relaxing the question, $s(n)$ could be regarded as the sum of the primes in the interval $[c,n]$ given a constant $c$.</p> http://mathoverflow.net/questions/63412/upper-bounds-for-the-sum-of-primes-n/63420#63420 Answer by Marc Palm for Upper bounds for the sum of primes <= n Marc Palm 2011-04-29T14:25:38Z 2011-04-29T15:20:29Z <p>Until a better answer appears. Here is a link:</p> <p><a href="http://mathworld.wolfram.com/PrimeSums.html" rel="nofollow">http://mathworld.wolfram.com/PrimeSums.html</a></p> <p>It says that</p> <p>$$s(p_n) \tilde \quad n^2 \log n /2.$$</p> <p>where $p_n$ is the $n$-th prime.</p> <p>Perhaps you want to look at the reference, and figure out if you can make the bound effective.</p> http://mathoverflow.net/questions/63412/upper-bounds-for-the-sum-of-primes-n/63426#63426 Answer by George Lowther for Upper bounds for the sum of primes <= n George Lowther 2011-04-29T15:15:51Z 2011-04-29T15:40:56Z <p>It is not difficult to calculate upper bounds on $s(n)$ from bounds on the prime counting function $\pi(n)$. Just use integration by parts, $$s(n) = \int_0^n x\,d\pi(x) = n\pi(n) - \int_0^n\pi(x)\,dx.$$ I'm not sure what the currently best known bounds for $\pi(x)$ are but, checking <a href="http://en.wikipedia.org/w/index.php?title=Prime_number_theorem&amp;oldid=425390559#Bounds_on_the_prime-counting_function" rel="nofollow">Wikipedia</a>, gives $$\frac{x}{\log x}\left(1+\frac{1}{\log x}\right) &lt; \pi(x) &lt; \frac{x}{\log x}\left(1+\frac{1}{\log x}+\frac{2.51}{(\log x)^2}\right)$$ with the left hand inequality holding for $x\ge599$ and the right hand holding for $x\ge355991$. So,</p> <p>$$s(n)\le \frac{n^2}{\log n}\left(1+\frac{1}{\log n}+\frac{2.51}{(\log n)^2}\right)-\int^n\left(1+\frac{1}{\log x}\right)\frac{x\,dx}{\log x}+c$$ (where $c$ is a constant which you can compute if you feel so inclined). Applying integration by parts,</p> <p>$$s(n)\le\frac{n^2}{2\log n}\left(1+\frac{1}{\log n}+\frac{5.02}{(\log n)^2}\right)-\frac12\int^n\left(1+\frac{2}{\log x}\right)\frac{x\,dx}{(\log x)^2}+c$$</p> <p>Bounding $\log x\le\log n$ in the integral gives a bound</p> <p>$$s(n)\le\frac{n^2}{2\log n}\left(1+\frac{1}{2\log n}+\frac{4.02}{(\log n)^2}\right)+c$$</p> <p>You can also take $c=0$ if you only require the bound to hold for $n\ge N$ (some $N$), since the term I neglected in the integral by applying $\log x\le \log n$ grows withuot bound, and will eventually dominate any constant term. Obviously, if you know any better bounds for $\pi(n)$ then you will get improved bounds for $s(n)$. For example, the same Wikipedia article linked to above states that $\left\vert\pi(x)-{\rm Li}(x)\right\vert\le\frac{\sqrt{x}\log x}{8\pi}$ for $x\ge2657$ under the assumption that the Riemann hypothesis holds.</p> http://mathoverflow.net/questions/63412/upper-bounds-for-the-sum-of-primes-n/63427#63427 Answer by GH for Upper bounds for the sum of primes <= n GH 2011-04-29T15:20:46Z 2011-04-29T15:20:46Z <p>By partial summation $$s(n) = n\pi(n)-\sum_{m=2}^{n-1}\pi(m)$$ so by the Prime Number Theorem $$s(n) = \frac{n^2}{\log n}-\sum_{m=2}^{n-1}\frac{m}{\log m}+O\left(\frac{n^2}{\log^2 n}\right).$$ The sum on the right is $$\sum_{m=2}^{n-1}\frac{m}{\log m} = \int_2^n \frac{x}{\log x}dx + O\left(\frac{n}{\log n}\right)$$ using the monotonicity properties of the integrand. Now the integral equals, by partial integration, $$\int_2^n \frac{x}{\log x}dx = \left[\frac{x^2}{2\log x}\right]_2^n + \int_2^n \frac{x}{2\log^2 x}dx = \frac{n^2}{2\log n} + O\left(\frac{n^2}{\log^2 n}\right).$$ Altogether we have $$s(n) = \frac{n^2}{2\log n} + O\left(\frac{n^2}{\log^2 n}\right).$$ This can be made more precise both numerically and theoretically.</p> http://mathoverflow.net/questions/63412/upper-bounds-for-the-sum-of-primes-n/65493#65493 Answer by Eric Bach for Upper bounds for the sum of primes <= n Eric Bach 2011-05-20T02:11:45Z 2013-04-26T12:54:20Z <p>There definitely are earlier references than our book. An asymptotic formula for</p> <p>$\sum_{p \leq x} p^a$</p> <p>is in T. Salát and S. Znám, <em>On the sums of the prime powers</em>, Acta Fac. Rer. Nat. Univ. Com. Math. 21 (1968), pp. 21-24. (Cited by Spearman &amp; Williams--I actually have not seen this paper.) It probably goes back further than that. The natural place to look would be Landau's "Primzahlen"--I forget the exact title--but I was unable to find that sum in there.</p> <p>Eric.</p> http://mathoverflow.net/questions/63412/upper-bounds-for-the-sum-of-primes-n/120304#120304 Answer by Nilotpal Sinha for Upper bounds for the sum of primes <= n Nilotpal Sinha 2013-01-30T11:12:53Z 2013-01-30T11:12:53Z <p>The following paper gives the asymptotic expansion of the sum of the first $n$ prime numbers. Hence for sufficiently large $n$, the first few positive and negative terms of the asymptotic expansion will give best upper and lower bound on the sum of primes.</p> <p><a href="http://arxiv.org/pdf/1011.1667.pdf" rel="nofollow">http://arxiv.org/pdf/1011.1667.pdf</a></p> <p>$$\sum_{r \le n}p_r = \frac{n^2}{2}\Bigg[\ln n + \ln\ln n - \frac{3}{2} + \frac{\ln\ln n}{\ln n} - \frac{3}{\ln n}- \frac{\ln^2 \ln n}{2\ln^2 n}$$</p> <p>$$+ \frac{7 \ln \ln n}{2\ln^2 n} - \frac{27}{4\ln^2 n} + o\Bigg(\frac{1}{\ln^2 n}\Bigg) \Bigg].$$</p>