Counting primes in residue classes
For coprime integers \(k\) and~\(\ell\) let \(\pi(x,k,\ell)\) count the primes \(p\leq x\) satisfying \(p\equiv\ell\) (mod~\(k\)). The theoretical result of the paper is that there is an algorithm which computes \(\pi(x,k,\ell)\) in time \(O(x^{2/3}/\log^2x)\), uniformly in \(k\) and~\(\ell\). In fact the time is the same as that for the algorithm for the computation of \(\pi(x)=\pi(x,1,1)\) given earlier by the first author and \textit{J.~Rivat} [Math. Comput. 65, 235--245 (1996; Zbl 0869.11068)], which is a refinement of the Lagarias-Miller-Odlyzko method, which in turn is an adaptation of the Meissel-Lehmer partial sieving method. Very roughly speaking, throughout the sieving procedure, a judicious choice in the division of labour is made; in particular, for suitable ranges of introduced parameters, a parallel sieve of all the invertible classes modulo \(k\) is applied from precomputed tables of primes. Chebyshev observed that the difference \(\delta(x)=\pi(x,4,3)-\pi(x,4,1)\) was more frequently positive, and Littlewood established that there are infinitely many sign changes for \(\delta(x)\). More recently \textit{M.~Rubinstein} and \textit{P.~Sarnak} [Exp. Math. 3, No. 3, 173--197 (1994; Zbl 0823.11050)] showed that, under a suitable generalisation of the Riemann Hypothesis, the set of integers~\(x\) for which \(\delta(x)<0\) has a small but positive logarithmic density. Meanwhile eight regions in which \(\delta(x)<0\) for most of the values \(x\) had been found. The algorithm here is implemented in C++, and a table of values for \(\pi(x,4,1)\) and \(\pi(x,4,3)\) is given for \(x=d{\times}10^j\) with \(1\leq d\leq 9\) and \(10\leq j\leq19\), and also for \(x=10^{20}\). Making use of the value of the said logarithmic density a search for values of \(x\) for which \(\delta(x)\) is relatively small is conducted in order to find regions where \(\delta(x)<0\); as pointed out by the authors, the search is thorough but not exhaustive. The eight known regions are found again, together with a new region near~\(x=10^{18}\), where \(\delta(x)=2561691\) is relatively small, but positive. The region concerned starts at \(9{\cdot}97{\times}10^{17}\) and extends to \(1{\cdot}005{\times}10^{18}\).
- Residue classes containing an unexpected number of primes
- A note on primes in certain residue classes
- On the residue class distribution of the number of prime divisors of an integer
- scientific article; zbMATH DE number 421695
- On integers whose number of prime divisors belongs to a given residue class
- Residuacity of primes
- The distribution of relatively \(r\)-prime integers in residue classes
- Explicit bounds for primes in residue classes
- scientific article; zbMATH DE number 733563
- Limiting properties of the distribution of primes in an arbitrarily large number of residue classes
- Biases in the Shanks—Rényi Prime Number Race
- Chebyshev's Bias
- Computing π(x): The Meissel-Lehmer Method
- Computing 𝜋(𝑥): the Meissel, Lehmer, Lagarias, Miller, Odlyzko method
- scientific article; zbMATH DE number 47601 (Why is no real title available?)
- Note on the Distribution of Prime Numbers
- On the exact number of primes less than a given limit
- On the Fluctuations of Littlewood for Primes of the Form 4n ± 1
- Zeros of Dirichlet \(L\)-functions near the real axis and Chebyshev's bias
- Detection of primes in the set of residues of divisors of a given number
- Sign changes in \(\pi_{q,a}(x) - \pi_{q,b}(x)\)
- VALEURS IMPAIRES DE LA FONCTION DE PARTITION p(n)
- The appearence of tens of billion of integers x with π24, 13 (x) < π24, 1 (x) in the vicinity of 1012.
- Zeroes of Dirichlet $L$-functions and irregularities in the distribution of primes
- Empirical verification of the even Goldbach conjecture and computation of prime gaps up to 4⋅10¹⁸
- An annotated bibliography for comparative prime number theory
This page was built for publication: Counting primes in residue classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4813598)
