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:
| \(\ds 4 - 1^2\) | \(=\) | \(\ds 3\) | which is prime | |||||||||||
| \(\ds 6 - 1^2\) | \(=\) | \(\ds 5\) | which is prime | |||||||||||
| \(\ds 8 - 1^2\) | \(=\) | \(\ds 7\) | which is prime |
$10$ cannot be expressed as $10 = m^2 + p$.
Thus $10$ is seen to be in this sequence.
| \(\ds 12 - 1^2\) | \(=\) | \(\ds 11\) | which is prime | |||||||||||
| \(\ds 14 - 1^2\) | \(=\) | \(\ds 13\) | which is prime | |||||||||||
| \(\ds 15 - 2^2\) | \(=\) | \(\ds 11\) | which is prime | |||||||||||
| \(\ds 16 - 3^2\) | \(=\) | \(\ds 7\) | which is prime | |||||||||||
| \(\ds 18 - 1^2\) | \(=\) | \(\ds 17\) | which is prime | |||||||||||
| \(\ds 20 - 1^2\) | \(=\) | \(\ds 19\) | which is prime | |||||||||||
| \(\ds 21 - 2^2\) | \(=\) | \(\ds 17\) | which is prime | |||||||||||
| \(\ds 22 - 3^2\) | \(=\) | \(\ds 13\) | which is prime | |||||||||||
| \(\ds 24 - 1^2\) | \(=\) | \(\ds 23\) | which is prime | |||||||||||
| \(\ds 26 - 3^2\) | \(=\) | \(\ds 17\) | which is prime | |||||||||||
| \(\ds 27 - 2^2\) | \(=\) | \(\ds 23\) | which is prime | |||||||||||
| \(\ds 28 - 3^2\) | \(=\) | \(\ds 19\) | which is prime | |||||||||||
| \(\ds 30 - 1^2\) | \(=\) | \(\ds 29\) | which is prime | |||||||||||
| \(\ds 32 - 1^2\) | \(=\) | \(\ds 31\) | which is prime | |||||||||||
| \(\ds 33 - 2^2\) | \(=\) | \(\ds 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
 | Work In Progress In particular: Design (or adoption) of a rigorous pseudocode needs to be done. Alternatively we may seek to stick with our existing technique for implement algorithms, and/or use a flow chart. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by completing it. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{WIP}} from the code. |
 | This needs considerable tedious hard slog to complete it. In particular: Tidy up the algorithm above. Do we demonstrate an instance of an computer program here? To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Finish}} from the code.If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page. |
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$