# Efficient ways to count primes satisfying Zhang's theorem

The theorem of Yitang Zhang states that there exist a finite $k \in \mathbb{N}$ such that there exist infinitely pairs of primes $(p,q)$ such that $|p - q| \leq k$. The statement that $k$ can be taken to be 2 is the twin primes conjecture. Currently, a polymath project was able to attain the value $k = 4680$.

Heuristically, based on the twin prime conjecture, one should obtain an estimate of the following type: let $\pi_k(x)$ be the counting functions of primes $p \leq x$ such that $p + k$ is also prime. Then Zhang's theorem implies the existence of some even $k \leq 4680$ such that $$\displaystyle \pi_k(n) \rightarrow \infty$$ and $\pi_k(x)$ should satisfy $$\displaystyle \pi_k(x) \gg \frac{x}{\log^2(x)}.$$

More should be true; indeed we should have an asymptotic of the form

$$\displaystyle \pi_k(x) \sim C \frac{x}{\log^2(x)}$$

for some constant $C > 0$. If $k = 2$, then $C = C_2$, the twin-prime constant.

My question is regarding the existence of efficient algorithms to search for large primes counted by $\pi_k(x)$. My understanding is that the current algorithm used to search for Mersenne primes of the form $2^p - 1$ (due to Lehmer) is efficient mostly because one simply needs to search for large $p$, then run a relatively efficient algorithm to determine the primality of $2^p - 1$. Obviously one does not expect the same level of efficiency with searching for primes counted by $\pi_k(x)$. Nonetheless, has anyone taken on this project? Specifically, has anyone been able to generate a list of large primes of Zhang-type other than existing lists made for twin primes?

-
My understanding is that Zhang's proof does not convert into an efficient algorithm. To find large twin primes or close-neighbor primes, the best way is probably to repeatedly choose numbers at random (biasing against having small prime factors) and simply test the two numbers for primality. – Greg Martin Oct 25 '13 at 13:26
Is there a nice writeup of the following problem? Given positive integers k and n, count the number of residue classes c such that gcd(c,n)=gcd(c+k,n)=1? Even if n were restricted to primorials, I would be happy to read such a writeup. Gerhard "Will Look At Small Pieces" Paseman, 2013.10.25 – Gerhard Paseman Oct 25 '13 at 15:28
It might be more challenging find a prime $P$ with a proof that there are no more before $P+4860.$ Is one known? It certainly seems likely that all the largest Mersenne primes have this property, however we are only able to discover their primality because of their special form. Testing $P+2310$ might be totally beyond out abilities at this point in time. So are there P small enough to let us check $(P,P+4680)$ for primes yet large enough that there is any reasonable chance that there might not be any there to find? – Aaron Meyerowitz Oct 26 '13 at 6:36