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!

  • $\begingroup$ 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). $\endgroup$ – Alex J Best Sep 2 '13 at 12:11
  • $\begingroup$ Presumably, you want a function which estimates this, not one that gives an exact count? $\endgroup$ – Thomas Andrews Sep 2 '13 at 12:17
  • $\begingroup$ 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*} $\endgroup$ – draks ... Sep 2 '13 at 12:22
  • $\begingroup$ @ThomasAndrews: Yes, I want to get an exact count. $\endgroup$ – Jiabin He Sep 2 '13 at 12:27
  • $\begingroup$ 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. $\endgroup$ – Thomas Andrews Sep 2 '13 at 12:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.