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

  • 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$ 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
    Apr 29, 2011 at 14:33

5 Answers 5


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.


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.


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.


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.


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


Until a better answer appears. Here is a link:


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.

  • $\begingroup$ So Michael Lugo's heuristic actually can be made effective... $\endgroup$
    – Marc Palm
    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
    Apr 29, 2011 at 15:11
  • $\begingroup$ Sorry, I have missed that difference. I did not read carefully. $\endgroup$
    – Marc Palm
    Apr 29, 2011 at 15:18
  • $\begingroup$ Fixed the mistake... $\endgroup$
    – Marc Palm
    Apr 29, 2011 at 15:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.