There is a well-known formula for the prime counting function $\pi(x)$: $$ \pi(x) = \pi(\sqrt x) -1 + \lfloor x\rfloor - \sum_{p<\sqrt x} \left\lfloor \frac xp\right\rfloor + \sum_{p,q<\sqrt x,p\ne q} \left\lfloor\frac x{pq}\right\rfloor-\ldots $$

Is there a similar formula to count only primes which are congruent to $1$ modulo $4$? Any other efficient way to find practically the number of such primes not exceeding a given $x$?


  • 1
    $\begingroup$ Dividing the above by $2$ is not a good enough approximation? $\endgroup$ – barak manos Oct 30 '16 at 7:49
  • 1
    $\begingroup$ @barak manos: The person who asked me needs an exact formula. For an approximation one does not need the formula in my post, just take $\rm li$ or something like that... $\endgroup$ – W-t-P Oct 30 '16 at 7:52
  • $\begingroup$ This answer might be relevant. $\endgroup$ – barak manos Oct 30 '16 at 7:52
  • $\begingroup$ Also, according to the abstract of this article, it's quite relevant (I haven't read the article itself, though). $\endgroup$ – Arthur Oct 30 '16 at 7:53
  • $\begingroup$ @barakmanos do you know the Dirichlet L-function $L(s,\chi_4) = \sum_{n=0}^\infty (2n-1)^{-s}(-1)^n$, the Dirichlet theorem on arithmetic progressions, and the fact $0 < L(s,\chi_4) < 1 \implies \log L(s,\chi_4) <0$ for $s > 1/2$ indicating that $\pi_4(x) < 0$ for most $x$ ? $\endgroup$ – reuns Oct 30 '16 at 19:20

Let $\displaystyle \text{lpf}(n) = \max_{p | n} p$ be the largest prime factor. The Möbius function $\mu(n)$ is defined by $$\sum_{d | n} \mu(d) = 1_{n = 1}$$ Therefore $$\sum_{d | n, \text{ lpf}(d) \le k} \mu(d) = \sum_{d | gcd(n,k!)}\mu(d) = 1_{gcd(n,k!) = 1}$$ Now it is clear that for $n < (k+1)^2$ : $gcd(n,k!) = 1 \Leftrightarrow n=1$ or $n$ is a prime $\in (k,(k+1)^2)$.

Hence for any $x \in [k,(k+1)^2)$ : $$\pi(x)-\pi(k)+1 = \sum_{n=1}^x 1_{gcd(n,k!) = 1} = \sum_{n=1}^x \ \sum_{d | n, \text{ lpf}(d) \le k} \mu(d) = \sum_{d=1, \text{ lpf}(d) \le k}^x \mu(d) \lfloor x/d\rfloor$$ which is the formula you wrote

For counting the primes $\equiv 1 \bmod 4$, use that $\chi_4(2n-1) = (-1)^n,\chi_4(2n)=0$ is completely multiplicative, so with $\pi_4(x) = \sum_{p \le x} \chi_4(p)$ you have $$\pi_4(x)-\pi_4(k)+1 = \sum_{n=1}^x \chi_4(n) 1_{gcd(n,k!) = 1} = \sum_{n=1}^x \chi_4(n) \ \sum_{d | n, \text{ lpf}(d) \le k} \mu(d)$$ $$ = \sum_{n=1}^x \ \sum_{d | n, \text{ lpf}(d) \le k} \chi_4(n/d)\chi_4(d)\mu(d)= \sum_{d=1, \text{ lpf}(d) \le k}^x \chi_4(d)\mu(d) \sum_{m=1}^{\lfloor x/d \rfloor} \chi_4(m)$$

Finally, letting $\displaystyle S_4(n) = \sum_{m=1}^n\chi_4(m)$ i.e. $S_4(4n+1)=S_4(4n+2)=1,S_4(4n+3)=S_4(4n)=0$

and $\displaystyle \Pi_{1,4}(x) = \sum_{p \le x, \ p \equiv 1 \bmod 4} 1 = \frac{\pi(x)+\pi_4(x)}{2}$

you get for any $x \in [k,(k+1)^2)$ : $$\boxed{\Pi_{1,4}(x)-\Pi_{1,4}(k)+1=\frac{1}{2}\sum_{d=1, \text{lpf}(d)\le k}^{x} \mu(d)(\lfloor x/d\rfloor+ \chi_4(d) S_4(\lfloor x/d\rfloor))}$$

  • $\begingroup$ Good stuff. But there seems to be a small typo, it should say $S_4(4n+1)=S_4(4n+2)=-1.$ $\endgroup$ – Reiner Martin Oct 12 '17 at 16:57

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.