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?

arethere 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? $\endgroup$ – Aaron Meyerowitz Oct 26 '13 at 6:36