Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Dirichlet's theorem on arithmetic progressions states that for any two positive integers a and b, if gcd(a,b) = 1 then the arithmetic progression $t(x)=ax+b$ $(x ≥ 0)$ contains infinitely many prime numbers.
For example, if a = 4 and b = 3, then the arithmetic progression is
3, 7, 11, 15, 19, 23, 27, 31, 35, ...,
Now,given $a\gt0,b\ge0$, and $U\ge L\ge0$, I want to find out an algorithm that can count count how many values of $t(x) = ax+b$ are prime, where $L ≤ x ≤ U$. Moreover, $aU+b\le10^{12}, U-L\le10^6$. Thanks in advance!

share|improve this question
It should be possible to adapt the sieve of Eratosthenes to count primes in an arithmetic progression, in fact this article jstor.org/stable/1967477 seems to do something of the sort (though I haven't read it). –  Alex J Best Sep 2 '13 at 12:11
Presumably, you want a function which estimates this, not one that gives an exact count? –  Thomas Andrews Sep 2 '13 at 12:17
With the help of Raymond Manzoni and Greg Martin I was able to derive an explicit formula for the number of primes of the form $4n+3$ in terms of (sums of) sums of Riemann's $R$ functions over roots of Riemann's $\zeta$ resp. Dirichlet $\beta$ function: \begin{align*} \pi^*(x;4,3)&=\sum_{k=0}^\infty 2^{-k-1}\left( \operatorname{R}(x^{1/2^{k}})-\sum_{\rho_\zeta} \operatorname{R}(x^{\rho_\zeta/2^k}) +\sum_{\rho_\beta} \operatorname{R}(x^{\rho_\beta/2^k}) \right) \end{align*} –  draks ... Sep 2 '13 at 12:22
@ThomasAndrews: Yes, I want to get an exact count. –  Jiabin He Sep 2 '13 at 12:27
Well, exactly counts are going to be hard to come by. Do you know the sorts of "exact counts" that count the simple case of $a=1,b=0$ - that is, all primes? They tend to look like @draks... formula. Not sure how computable that formula is. –  Thomas Andrews Sep 2 '13 at 12:35

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.