Problem 1259

Solution:

Answer: 1462105

The Hardy-Littlewood conjecture states that given a set $A$ of integers, the number of integers $x$ such that $x+a$ is a prime for all $a \in A$ is
$$\frac{x}{(\ln x)^{|A|}} \prod_{p} \frac{1-\frac{w(p ; A)}{p}}{\left(1-\frac{1}{p}\right)^{k}}(1+o(1))$$
where $w(p ; A)$ is the number of distinct residues of $A$ modulo $p$ and the $o(1)$ term goes to 0 as $x$ goes to infinity. Note that for the 4 tuples of the form $(0, \pm 2, \pm 6)$, $w(p ; A)=3$, and using the approximation $\frac{1-k / p}{(1-1 / p)^{k}} \approx 1-\binom{k}{2} / p^{2} \approx\left(1-\frac{1}{p^{2}}\right)^{\binom{k}{2}}$, we have
$$\prod_{p>3} \frac{1-\frac{k}{p}}{\left(1-\frac{1}{p}\right)^{k}} \approx\left(\frac{6}{\pi^{2}}\right)^{\binom{k}{2}} \cdot\left(\frac{4}{3}\right)^{\binom{k}{2}}\left(\frac{9}{8}\right)^{\binom{k}{2}} \approx\left(\frac{9}{10}\right)^{\binom{k}{2}}$$
Applying this for the four sets $A=(0, \pm 2, \pm 6)$, $x=10^{9}$ (and approximating $\ln x=20$ and just taking the $p=2$ and $p=3$ terms), we get the approximate answer
$$4 \cdot \frac{10^{9}}{20^{3}} \frac{1-\frac{1}{2}}{\left(\frac{1}{2}\right)^{3}} \frac{1-\frac{2}{3}}{\left(\frac{1}{3}\right)^{3}}\left(\frac{9}{10}\right)^{3}=1640250$$
One improvement we can make is to remove the double-counted tuples, in particular, integers $x$ such that $x, x+6, x-6$, and one of $x \pm 2$ is prime. Again by the Hardy-Littlewood conjecture, the number of such $x$ is approximately (using the same approximations)
$$2 \cdot \frac{10^{9}}{20^{4}} \frac{1-\frac{1}{2}}{\left(\frac{1}{2}\right)^{4}} \frac{1-\frac{2}{3}}{\left(\frac{1}{3}\right)^{4}}\left(\frac{9}{10}\right)^{6} \approx 90000$$
Subtracting gives an estimate of about 1550000. Note that this is still an overestimate, as $\ln 10^{9}$ is actually about 20.7 and $\frac{1-k / p}{(1-1 / p)^{k}}<\left(1-\frac{1}{p^{2}}\right)^{\binom{k}{2}}$.

Here is the $\mathrm{C}++$ code that we used to generate the answer:

```
#include<iostream>
#include<cstring> // memset
using namespace std;
const int MAXN = 1e9;
bool is_prime[MAXN + 6];
int main(){
// Sieve of Eratosthenes
memset(is_prime, true, sizeof(is_prime));
is_prime[0] = is_prime[1] = false;
for (int i=2; i<MAXN + 6; i++){
if (is_prime*){
for (int j=2 * i; j < MAXN + 6; j += i){
is_prime[j] = false;
}
}
}
// Count twin sexy primes.
int ans = 1; // 5 is the only twin sexy prime < 6.
for (int i=6; i<MAXN; i++){
if (is_prime*
&& (is_prime[i-6] || is_prime[i+6])
&& (is_prime[i-2] || is_prime[i+2])) {
ans++;
}
}
cout << ans << endl;
return 0;
}
```