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
Additional Information
- Marc Deléglise
- Affiliation: Institut Girard Desargues, Université Lyon I, 21, avenue Claude Bernard, 69622 Villeurbanne Cedex, France
- Email: Marc.Deleglise@igd.univ-lyon1.fr
- Pierre Dusart
- Affiliation: LACO, Département de Mathématiques, avenue Albert Thomas, 87060 Limoges Cedex, France
- Email: dusart@unilim.fr
- Xavier-François Roblot
- Affiliation: Institut Girard Desargues, Université Lyon I, 21, avenue Claude Bernard, 69622 Villeurbanne Cedex, France
- Email: Xavier.Roblot@igd.univ-lyon1.fr
- Received by editor(s): November 7, 2001
- Received by editor(s) in revised form: October 24, 2002
- Published electronically: February 25, 2004
- © Copyright 2004 American Mathematical Society
- Journal: Math. Comp. 73 (2004), 1565-1575
- MSC (2000): Primary 11Y40; Secondary 11A41
- DOI: https://doi.org/10.1090/S0025-5718-04-01649-7
- MathSciNet review: 2047102