15
$\begingroup$

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) < (1+\epsilon)\frac{n^2}{\log{n}}.$

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

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

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ I would have thought the sum of the first $n$ primes was asymptotically equivalent to $(n^2 \log n)/2$. (The $n$th prime is near $n \log n$, so the sum of the integers up to the $n$th prime is near $(n \log n)^2/2$, but only a proportion $1/\log n$ of the summands are prime. $\endgroup$
    – Michael Lugo
    Commented Apr 29, 2011 at 14:28
  • $\begingroup$ Did you try already to use Weil's explicit formula. Appropiated choosen tex functions, e.g. $e^{x tanh(x)} e^{-x^2 \delta}$ should give you an upper bound. $\endgroup$
    – Marc Palm
    Commented Apr 29, 2011 at 14:33

5 Answers 5

Reset to default
26
$\begingroup$

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.

Improve this answer
$\endgroup$
19
$\begingroup$

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 Wikipedia, gives $$ \frac{x}{\log x}\left(1+\frac{1}{\log x}\right) < \pi(x) < \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,

$$ 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,

$$ 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 $$

Bounding $\log x\le\log n$ in the integral gives a bound

$$ s(n)\le\frac{n^2}{2\log n}\left(1+\frac{1}{2\log n}+\frac{4.02}{(\log n)^2}\right)+c $$

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.

Improve this answer
$\endgroup$
0
12
$\begingroup$

There definitely are earlier references than our book. An asymptotic formula for

$\sum_{p \leq x} p^a$

is in T. Salát and S. Znám, On the sums of the prime powers, Acta Fac. Rer. Nat. Univ. Com. Math. 21 (1968), pp. 21-24.

Improve this answer
$\endgroup$
2
8
$\begingroup$

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.

http://arxiv.org/pdf/1011.1667.pdf

$$ \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} $$

$$ + \frac{7 \ln \ln n}{2\ln^2 n} - \frac{27}{4\ln^2 n} + o\Bigg(\frac{1}{\ln^2 n}\Bigg) \Bigg]. $$

Improve this answer
$\endgroup$
3
$\begingroup$

Until a better answer appears. Here is a link:

http://mathworld.wolfram.com/PrimeSums.html

It says that

$$s(p_n) \sim \; n^2 \log n /2.$$

where $p_n$ is the $n$-th prime.

Perhaps you want to look at the reference, and figure out if you can make the bound effective.

Improve this answer
$\endgroup$
4
  • $\begingroup$ So Michael Lugo's heuristic actually can be made effective... $\endgroup$
    – Marc Palm
    Commented Apr 29, 2011 at 15:08
  • 1
    $\begingroup$ Not exactly: there is a difference between the sum of primes less than or equal to $n$, and the sum of the $n$ first primes. I must have missed something: how could $s(n) \sim n^2 \ln(n)/2$ have not be proven before 1996 by Bach and Shallit? I do not see what is wrong with the fact that, since, $p_n \sim n \ln(n)$ (prime number theorem), one has: $\sum_{k=1}^n p_k \sim \sum_{k=1}^n k \ln(k) \sim \int_1^n t\ln(t) \mathrm{d}t \sim n^2\ln(n)/2$ $\endgroup$
    – Bernikov
    Commented Apr 29, 2011 at 15:11
  • $\begingroup$ Sorry, I have missed that difference. I did not read carefully. $\endgroup$
    – Marc Palm
    Commented Apr 29, 2011 at 15:18
  • $\begingroup$ Fixed the mistake... $\endgroup$
    – Marc Palm
    Commented Apr 29, 2011 at 15:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .