I ask this question based on a comment of David Speyer in another question. What primes are of the form
where $p$ and $q$ are prime?
The first prime not apparently of this form is 17. The Diophantine equation
has solutions following a linear recurrence relation which has no primes in the first 1000 terms (only $(\pm1, 1)$ seeds may contain primes). But perhaps there is a better way to go about this?
I think for the equation:
It is necessary to record decisions. We will use the solutions of the Pell equation.
And then the solutions are of the form: