Can anyone help me with references to the current fastest algorithms for counting the exact sum of primes less than some number n? I'm specifically curious about the best case running times, of course. I'm pretty familiar with the various fast algorithms for prime counting, but I'm having a harder time tracking down sum of prime algorithms…
Fastest Algorithm to Compute the Sum of Primes
algorithmscomputer-algebrant.number-theoryprime numbers
Related Solutions
I'll address Joel's edited question of getting good asymptotics on RH. The argument below is essentially due to Selberg, but this is not quite what he does and I haven't seen it presented this way in the literature. The natural problem is to consider the coefficients of $(\log \zeta (s))^k/k!$ rather than numbers with exactly $k$ prime factors. Note that for $k=1$ and $2$ the two objects are closely related, and some obvious but unpleasant combinatorics is needed for larger $k$.
Thus we want to compute $$ \frac{1}{2\pi i} \frac{1}{k!} \int_{c-i\infty}^{c+i\infty} (\log \zeta(s))^k x^s \frac{ds}{s}, $$ where the integral is taken over some line with $c>1$. Now we want to shift contours as usual, but we need to be careful because logarithmic singularities are involved rather than just poles. First choose $c$ just a little bigger than $1$ and truncate the integral at some height $T$. Then deform the contour as follows: Take a slit along the real axis from $1/2+\epsilon$ to $1$ with a line just above and a line just below the slit, and then line segments from $1/2+\epsilon$ to $1/2+\epsilon +iT$ and then from there to $c+iT$, and similar line segments below the real axis. If one assumes RH, the errors in truncation together with all the integrals except for the ones above and below the slit can be bounded by $x^{1/2+\epsilon}$. Thus we conclude that our integral equals, with error $O(x^{1/2+\epsilon})$, $$ -\frac{1}{2\pi i} \frac{1}{k!} \int_{1/2+\epsilon}^{1} \Big((\log \zeta(\sigma+ 0^+ i))^k - (\log \zeta(\sigma+0^- i))^k \Big) \frac{x^\sigma}{\sigma} d\sigma. $$ Here I use $0^+i$ to denote the upper part of the slit, and $0^-$ to denote the lower part. The two terms don't cancel out because of the change in the argument of $\zeta$ above and below the slit. Note that above the slit one has $\log \zeta(\sigma+0^+i) = \log |\zeta(\sigma)| - i\pi$ and below the slit one has $\log \zeta(\sigma+0^-i) = \log |\zeta(\sigma)| +i \pi$. Thus we find that the desired answer is $$ \frac{1}{\pi k!} \int_{1/2+\epsilon}^1 \text{Im} (\log |\zeta(\sigma)| +i\pi)^k \frac{x^{\sigma}}{\sigma} d\sigma + O(x^{1/2+\epsilon}). $$
To appreciate what this means, consider first the prime number theorem which is the case $k=1$. From above we see that the main term is $$ \int_{1/2+\epsilon}^{1} \frac{x^{\sigma}}{\sigma} d\sigma, $$ and a change of variables produces $\text{Li}(x)$. When $k=2$ (essentially the case of $\pi_2(x)$) the work above gives $$ \int_{1/2+\epsilon}^1 \log |\zeta(\sigma)| \frac{x^{\sigma}}{\sigma} d\sigma + O(x^{1/2+\epsilon}). $$ The leading order asymptotics come from $\sigma$ very close to $1$, on the scale of $1-c/\log x$, and then $\log |\zeta(\sigma)|$ will contribute the extra $\log \log x$. One can obtain more precise asymptotic expansions etc from this expression.
Let me also note that one can make this argument unconditional using the classical zero free region, and it may be worthwhile carrying this out. The usual way in which such results are carried out in the literature is to start with asymptotics for coefficients of $\zeta(s)^z$ for complex $z$, and then to use the saddle point method to identify from this numbers with $k$ prime factors. This is Selberg's argument with various elaborations, most notably by Hildebrand and Tenenbaum. The argument above seems to be a shortcut and may produce better results. It would be surprising if nobody had thought of it before, but at any rate I haven't seen it.
I don't know if this might interest you, but there is a nice formula due to Lifchitz which allows to compute the parity of $\pi(x)$ in $O(\sqrt{x}\log x)$: if $\Pi(x)$ represent the number of prime powers up to $x$ then
$$ \Pi(x) \equiv \sum_{m\leq \sqrt{x}} \mu(m) \sum_{n\leq \sqrt(x/m^2)} \left\lfloor\frac{x}{nm^2}\right\rfloor \pmod{2} $$
This is more like a comment, but I can't comment as I have not enough reputation.
Related Question
- [Math] Explicit formula for Riemann zeros counting function
- Bounding the Error in Estimating a Relative Totient Function
- Dirichlet Hyperbola Method – Relationship with Prime Counting and Mertens Function
- [Math] Finding primes using Euler’s sum of divisors recurrence relation
- [Math] Infinitely many primes, and Mobius randomness in sparse sets
Best Answer
Deléglise-Dusart-Roblot [1] give an algorithm which determines $\pi(x,k,l)$, the number of primes up to $x$ that are congruent to $l$ modulo $k,$ in time $O(x^{2/3}/\log^2x).$ Using this algorithm to count the number of primes in all residue classes $k<2\log x$ takes $$1+\sum_{p<2\log x}(p-2)\sim\frac{2\log^2x}{\log\log x}$$ invocations of Deléglise-Dusart-Roblot for a total of $O(x^{2/3}/\log\log x)$ time.
This allows one to determine the value of $\sum_{p\le x}p$ mod all primes up to $2\log x$ and hence, by the Prime Number Theorem and Chinese Remainder Theorem, the value of the sum mod $\exp(\vartheta(2\log x))=x^2(1+o(1)).$ Together with bounds on the value of $\sum_{p\le x}p$ [2], this allows the computation of the sum.
Note that the primes slightly beyond $2\log x$ may be required depending on the value of $\vartheta(2\log x).$ Practically speaking, except for $x$ tiny, $2\log x+\log x/\log\log x$ suffices. This does not change the asymptotics.
I do not know if it is possible to modify the Lagarias-Odlyzko analytic formula [3] to count in residue classes. If so, this would allow an $O(x^{1/2+o(1)})$ algorithm.
References
[1] Marc Deléglise, Pierre Dusart, and Xavier-François Roblot, Counting primes in residue classes, Mathematics of Computation 73:247 (2004), pp. 1565-1575. doi 10.1.1.100.779
[2] Nilotpal Kanti Sinha, On the asymptotic expansion of the sum of the first n primes (2010).
[3] J. C. Lagarias and A. M. Odlyzko, Computing $\pi(x)$: An analytic method, Journal of Algorithms 8 (1987), pp. 173-191.