Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Counting primes in residue classes

Authors: Marc Deléglise, Pierre Dusart and Xavier-François Roblot
Translated by:
Journal: Math. Comp. 73 (2004), 1565-1575
MSC (2000): Primary 11Y40; Secondary 11A41
Published electronically: February 25, 2004
MathSciNet review: 2047102
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [BH78] C. Bays and R. H. Hudson, On the fluctuations of Littlewood for primes of the form $4n\not=1$, Math. Comp. 32 (1978), 281-286. MR 57:16174
  • [BFHR01] C. Bays, K. Ford, R. H. Hudson and M. Rubinstein, Zeros of Dirichlet $L$-functions near the real axis and Chebyshev's bias, J. Number Theory 87 (2001), 54-76. MR 2001m:11148
  • [DR96] M. Deléglise and J Rivat, Computing $\pi(x)$: the Meissel, Lehmer, Lagarias, Miller, Odlyzko method, Math. Comp. 65 (1996), 235-245. MR 96d:11139
  • [FM00] A. Feuerverger and G. Martin, Biases in the Shanks-Rényi prime number race, Experiment. Math. 9 (2000), 535-570. MR 2002d:11111
  • [Gou01] X. Gourdon,
  • [Ing90] A. E. Ingham, The distribution of prime numbers, Cambridge University Press, 1990. MR 91f:11064
  • [LMO85] J. C. Lagarias, V. S. Miller and A. M. Odlyzko, Computing $\pi(x)$: the Meissel-Lehmer method, Math. Comp. 44 (1985), 537-560. MR 86h:11111
  • [Lee57] J. Leech, Note on the distribution of prime numbers, J. London Math. Soc. 32 (1957), 56-58. MR 18:642d
  • [Leh59] D. H. Lehmer, On the exact number of primes less than a given limit, Illinois J. Math. 3 (1959), 381-388. MR 21:5613
  • [Lit14] J. E. Littlewood, Sur la distribution des nombres premiers, C. R. Acad. Sci. Paris 158 (1914), 358-372.
  • [RS94] M. Rubinstein and P. Sarnak, Chebyshev's Bias, Experiment. Math. 3 (1994), 173-197. MR 96d:11099

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y40, 11A41

Retrieve articles in all journals with MSC (2000): 11Y40, 11A41

Additional Information

Marc Deléglise
Affiliation: Institut Girard Desargues, Université Lyon I, 21, avenue Claude Bernard, 69622 Villeurbanne Cedex, France

Pierre Dusart
Affiliation: LACO, Département de Mathématiques, avenue Albert Thomas, 87060 Limoges Cedex, France

Xavier-François Roblot
Affiliation: Institut Girard Desargues, Université Lyon I, 21, avenue Claude Bernard, 69622 Villeurbanne Cedex, France

Keywords: Prime numbers, residue classes, Chebyshev's bias
Received by editor(s): November 7, 2001
Received by editor(s) in revised form: October 24, 2002
Published electronically: February 25, 2004
Article copyright: © Copyright 2004 American Mathematical Society