36. [25] A prime number $p$ is twin if at least one of $p+2$ or $p-2$ is prime and sexy if at least one of $p+6$ and $p-6$ is prime.
How many sexy twin primes (i.e. primes that are both twin and sexy) are there less than $10^{9}$ ? Express your answer as a positive integer $N$ in decimal notation; for example, 521495223. If your answer is in this form, your score for this problem will be $\max \left\{0,25-\left\lfloor\frac{1}{10000}|A-N|\right\rfloor\right\}$, where $A$ is the actual answer to this problem. Otherwise, your score will be zero.
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}}
#include // 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[i]){
            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[i]
            && (is_prime[i-6] || is_prime[i+6])
            && (is_prime[i-2] || is_prime[i+2])) {
                ans++;
        }
    }
    cout << ans << endl;
    return 0;
}
```