Non-Square Positive Integers not Sum of Square and Prime

Conjecture

The sequence of (strictly) positive integers which are not square and not the sum of a square and a prime is believed to be complete:

$10, 34, 58, 85, 91, 130, 214, 226, 370, 526, 706, 730, 771, 1255, 1351, 1414, 1906, 2986, 3676, 9634, 21679$

Progress

From Square of n such that 2n-1 is Composite is not Sum of Square and Prime, $n^2$ is the sum of a square and a prime if and only if $2 n - 1$ composite.

Hence the question is specifically about non-squares.

No prime number is in this sequence, as trivially:

$p = p + 0^2$

and so is the sum of a prime (itself), and $0^2$, which is square.

Each non-square composite $n \in \Z$ can be tested by subtracting successive squares less than $n$ and investigating whether a prime can result.

In the following, the smallest $m$ such that $n - m^2 = p$ is shown where such a $p$ exists.

Otherwise the nonexistence of such a $p$ is demonstrated explicitly.

As follows:

 $\displaystyle 4 - 1^2$ $=$ $\displaystyle 3$ which is prime $\displaystyle 6 - 1^2$ $=$ $\displaystyle 5$ which is prime $\displaystyle 8 - 1^2$ $=$ $\displaystyle 7$ which is prime

Thus $10$ is seen to be in this sequence.

 $\displaystyle 12 - 1^2$ $=$ $\displaystyle 11$ which is prime $\displaystyle 14 - 1^2$ $=$ $\displaystyle 13$ which is prime $\displaystyle 15 - 2^2$ $=$ $\displaystyle 11$ which is prime $\displaystyle 16 - 3^2$ $=$ $\displaystyle 7$ which is prime $\displaystyle 18 - 1^2$ $=$ $\displaystyle 17$ which is prime $\displaystyle 20 - 1^2$ $=$ $\displaystyle 19$ which is prime $\displaystyle 21 - 2^2$ $=$ $\displaystyle 17$ which is prime $\displaystyle 22 - 3^2$ $=$ $\displaystyle 13$ which is prime $\displaystyle 24 - 1^2$ $=$ $\displaystyle 23$ which is prime $\displaystyle 26 - 3^2$ $=$ $\displaystyle 17$ which is prime $\displaystyle 27 - 2^2$ $=$ $\displaystyle 23$ which is prime $\displaystyle 28 - 3^2$ $=$ $\displaystyle 19$ which is prime $\displaystyle 30 - 1^2$ $=$ $\displaystyle 29$ which is prime $\displaystyle 32 - 1^2$ $=$ $\displaystyle 31$ which is prime $\displaystyle 33 - 2^2$ $=$ $\displaystyle 29$ which is prime

Thus $34$ is seen to be in this sequence.

Similarly:

Thus $58$ is seen to be in this sequence.

This establishes the pattern.

The algorithm for determining whether a particular $n$ belongs to this sequence can be defined in pseudocode as follows:

For n := 1, loop indefinitely, incrementing by 1:
Is n prime? If so, continue to the next n
Is n square? If so, continue to the next n
For m := 1, incrementing by 1 until m^2 > n:
Is n - n^2 prime? If so, continue to the next n
Next m
Next n


Examples

10

$10$ cannot be expressed as the sum of a square and a prime.

34

$34$ cannot be expressed as the sum of a square and a prime.

58

$58$ cannot be expressed as the sum of a square and a prime.

Historical Note

G.H. Hardy and J.E. Littlewood made this conjecture in $1923$.

As reported in On-Line Encyclopedia of Integer Sequences (N. J. A. Sloane (Ed.), 2008), this sequence is:

Almost certainly finite; no other terms below ... $3 \, 000 \, 000 \, 000$