If $p,q$ are both odd, then mod 2, the sequence goes: $1,1,0,1,1,0,1,1,0,...$ So $x_{3k}$ is even, and cannot be $-3$. Therefore, either $p=2$ or $q=2$. If both are $2$, then all terms past the second are even, so exactly one is $2$. Next, mod $x_3=p^2-q$ the sequence goes: $1,p,0,-qp,-qp^2,0,q^2p^2,p^3q^2,0,...$, easy to find the general term of the sequence, and more importantly, it is easy to show that we have $x_{3k}$ is divisible by $x_3$. Thus, $x_3$ is either $3$ or $-3$. $p=2$ gives $q=1,7$, but $1$ is not prime, so $q=7$. $q=2$ does not give a $p$ that works. Thus, $p=2$, $q=7$ must be the candidate. To see that it is indeed the solution, note that $x_3=2^2-7=-3$. Cheers, Rofler Edit: Thank you uglysolutions, if it is $1$ then we get $p=2$, $q=3$, and if it is $-1$ then we get $p=2$, $q=5$ as the only possibilities. The first of these makes the sequence mod 3 $1,2,1,2,.....$ so cannot make $0$ mod 3, and the second sequence I don't actually know about... I haven't actually tried, but I am pretty sure that it is easy to show it never hits $-3$ because of the magnitude of the terms (more specifically, we can consider the characteristic polynomial that generates the sequence of every third term, and show this recurrence creates a sequence which has non-decreasing magnitude).

Rofler wrote: and more importantly, it is easy to show that we have $x_{3k}$ is divisible by $x_3$. Thus, $x_3$ is either $3$ or $-3$. Am I missing something here or $x_3$ could also be $\pm 1$? (It's not hard to discard these cases, though)