# Counting primes $p\equiv 1\pmod 4$

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$?

Thanks!

• Dividing the above by $2$ is not a good enough approximation? – barak manos Oct 30 '16 at 7:49
• @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... – W-t-P Oct 30 '16 at 7:52
• This answer might be relevant. – barak manos Oct 30 '16 at 7:52
• Also, according to the abstract of this article, it's quite relevant (I haven't read the article itself, though). – Arthur Oct 30 '16 at 7:53
• @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$ ? – 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))}$$

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