, 2024

Solution:

If $x \leq 10^{6}$, then $2x^{2}-1 < 2 \cdot 10^{12}$. The density of prime numbers up to $2 \cdot 10^{12}$ is roughly
$$\frac{1}{\ln \left(2 \cdot 10^{12}\right)-1} \approx 0.0366$$
However, $2x^{2}-1$ can never be divisible by $2$, $3$, or $5$. Only $\frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = \frac{4}{15}$ of numbers are not divisible by $2$, $3$, or $5$, including all of the primes, so the density of primes among such numbers is a factor of $\frac{15}{4}$ higher. Among the $10^{6}$ possible values of $x$, we get an estimate of
$$\frac{15}{4} \cdot 0.0366 \cdot 10^{6} = 137250$$

To refine this estimate further, observe that the values of $2x^{2}-1$ are not uniformly distributed from $1$ to $2 \cdot 10^{12}$. Their average is very close to $\frac{2}{3} \cdot 10^{12}$, so as a crude estimate, we can take the density of prime numbers up to $\frac{4}{3} \cdot 10^{12}$ instead:
$$\frac{1}{\ln \left(\frac{4}{3} \cdot 10^{12}\right)-1} \approx 0.03715$$
This gives us an estimate of
$$\frac{15}{4} \cdot 0.03715 \cdot 10^{6} \approx 139313$$

Using sage, one can easily obtain the exact answer by the following code.
```
cnt = 0
for x in range(1, 10^6+1):
if is_prime(2*x^2-1):
cnt += 1
print(cnt)
```