Non-Square Positive Integers not Sum of Square and Prime

From ProofWiki
Jump to navigation Jump to search

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$