# What is an example of positive integer that cannot be written as $p+a^2$, with $p$ prime or 1 and $a \geq 0$?

What is an example of positive integer that cannot be written as $p+a^2$, with $p$ prime or 1 and $a \geq 0$?

This should be simple, but every example I've come up with so far seems to satisfy the conjecture. Maybe there's a systematic way of finding counterexamples I'm not aware of?

-
Note also Hardy & Littlewood's Conjecture H, which implies that there are only finitely many counterexamples other than squares and squares plus one. (There are probably only finitely many counterexamples that are squares plus one as well, but H-L didn't comment on that form.) – Charles Nov 5 '11 at 17:55

Simply checking every positive integer in order quickly reveals that $25$ is a counterexample.

-
Extending this observation: try your luck with squares! $n^2-a^2$ with $a<n$ can be a prime only, if $a=n-1$, so... $64$ is another counterexample. – Jyrki Lahtonen Nov 5 '11 at 17:48
Related: oeis.org/A014090, which are counterexamples unless they are one more than a square. – Charles Nov 5 '11 at 17:51