Counting primes in residue classes

Deléglise, Marc; Dusart, Pierre; Roblot, Xavier-François

doi:10.1090/S0025-5718-04-01649-7

Counting primes in residue classes
HTML articles powered by AMS MathViewer

by Marc Deléglise, Pierre Dusart and Xavier-François Roblot PDF

Math. Comp. 73 (2004), 1565-1575 Request permission

Abstract:

We explain how the Meissel-Lehmer-Lagarias-Miller-Odlyzko method for computing $\pi (x)$ can be used for computing efficiently $\pi (x,k,l)$, the number of primes congruent to $l$ modulo $k$ up to $x$. As an application, we computed the number of prime numbers of the form $4n \pm 1$ less than $x$ for several values of $x$ up to $10^{20}$ and found a new region where $\pi (x,4,3)$ is less than $\pi (x,4,1)$ near $x = 10^{18}$.

References

Carter Bays and Richard H. Hudson, On the fluctuations of Littlewood for primes of the form $4n\not =1$, Math. Comp. 32 (1978), no. 141, 281–286. MR 476615, DOI 10.1090/S0025-5718-1978-0476615-8
Carter Bays, Kevin Ford, Richard H. Hudson, and Michael Rubinstein, Zeros of Dirichlet $L$-functions near the real axis and Chebyshev’s bias, J. Number Theory 87 (2001), no. 1, 54–76. MR 1816036, DOI 10.1006/jnth.2000.2601
M. Deléglise and J. Rivat, Computing $\pi (x)$: the Meissel, Lehmer, Lagarias, Miller, Odlyzko method, Math. Comp. 65 (1996), no. 213, 235–245. MR 1322888, DOI 10.1090/S0025-5718-96-00674-6
Andrey Feuerverger and Greg Martin, Biases in the Shanks-Rényi prime number race, Experiment. Math. 9 (2000), no. 4, 535–570. MR 1806291
X. Gourdon, http://numbers.computation.free.fr/Constants/Primes/Pix/
A. E. Ingham, The distribution of prime numbers, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1990. Reprint of the 1932 original; With a foreword by R. C. Vaughan. MR 1074573
J. C. Lagarias, V. S. Miller, and A. M. Odlyzko, Computing $\pi (x)$: the Meissel-Lehmer method, Math. Comp. 44 (1985), no. 170, 537–560. MR 777285, DOI 10.1090/S0025-5718-1985-0777285-5
Cahit Arf, Untersuchungen über reinverzweigte Erweiterungen diskret bewerteter perfekter Körper, J. Reine Angew. Math. 181 (1939), 1–44 (German). MR 18, DOI 10.1515/crll.1940.181.1
D. H. Lehmer, On the exact number of primes less than a given limit, Illinois J. Math. 3 (1959), 381–388. MR 106883
J. E. Littlewood, Sur la distribution des nombres premiers, C. R. Acad. Sci. Paris 158 (1914), 358–372.
Michael Rubinstein and Peter Sarnak, Chebyshev’s bias, Experiment. Math. 3 (1994), no. 3, 173–197. MR 1329368