We wish to find the set of natural numbers that cannot be expressed as a difference between a square and a prime.
$1 = 2^2 - 3$
$2 = 3^2 - 7$
$3 = 4^2 - 13$
and so on.
The smallest such number is $16$. The proof that $16$ cannot be expressed as a difference of a square and a prime:
Let $r^2 - p = 16$ for natural number $r$ and prime $p$
$\implies (r-4)(r+4) = p$
$\implies r-4 = 1$ since the two factors of $p$ are $p$ and $1$
$\implies r = 5$ but then $r + 4 = 9$ which is not a prime.
In general, this is true for all $n^2$ where $2n + 1$ is composite since the same reasoning applies. Therefore $49, 100, 144, 169..$ can be seen to belong to this set.
The question is whether all the numbers which cannot be expressed like this are of this form i.e. $n^2$ where $2n + 1$ is composite. A brute force search shows that this holds true for numbers less than 10000.