# 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$

This sequence is A020495 in the On-Line Encyclopedia of Integer Sequences (N. J. A. Sloane (Ed.), 2008).

## 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 |

$10$ cannot be expressed as $10 = m^2 + p$.

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 |

$34$ cannot be expressed as $34 = m^2 + p$.

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

Similarly:

$58$ cannot be expressed as $58 = m^2 + p$.

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 Add n to the sequence 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$*