Sign up ×
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|cite|improve this question
It should be possible to adapt the sieve of Eratosthenes to count primes in an arithmetic progression, in fact this article 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.