9
$\begingroup$

We wish to find the set of natural numbers that cannot be expressed as a difference between a square and a prime.

e.g.

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

Improve this question
$\endgroup$
3
  • $\begingroup$ A similar question is asked at math.stackexchange.com/questions/613256/… $\endgroup$
    – A.K.
    May 23, 2014 at 13:10
  • $\begingroup$ I dont konw what's the question,if is this: "The question is whether all the numbers which cannot be expressed like this are of this form i.e. n2 where 2n+1 is composite.", my answer is : yes,it is. If $2n+1$ is composite,$\ n$ must of the form $2ij + i + j,\ i, j \in\mathbb{Z},\ 1 \le i \le j\ $, see [Sieve of Sundaram](en.wikipedia.org/wiki/Sieve_of_Sundaram). Let $n = 2ij + i + j,\ $this question is equivalent to prove :$(n+x)^2 - n^2 $ is composite,where $x \in\mathbb{Z^+}$, this is a elementary question, I dont understand this is related to some conjecture. $\endgroup$
    – Mike
    May 24, 2014 at 6:01
  • 1
    $\begingroup$ @Mike: How do you show that a number that cannot be expressed like this must be a square in the first place? $\endgroup$
    – Emil Jeřábek
    May 24, 2014 at 10:44

2 Answers 2

Reset to default
20
$\begingroup$

We have a representation $m=x^2-p$ where $m$ and $x$ are positive integers and $p$ is a prime if and only if there is a prime of the form $x^2-m$. Little is known about primes of the form $x^2-m$; it has not been proved for any fixed value of $m$ that there are infinitely many such primes. However, Bunyakovsky's conjecture (or in fact a special case of it) would imply that $x^2-m$ is prime for infinitely many $x$ unless $m$ is a square. So, if we assume this conjecture, every non-square is the difference of a square and a prime. And if $m=n^2$ is a square, then clearly the representation is possible if and only if $2n+1$ is a prime.

It is of course a weaker claim that the sequence $x^2-m$ contains one prime than infinitely many, but proving this weaker statement for all non-squares $m$ might be almost as hard as proving the stronger statement. For example, proving Dirichlet's theorem about primes in arithmetic progressions is esentially as hard as showing that the sequence $an+b$ contains at least one prime for all coprime $a$ and $b$.

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ I assume this means that the problem is open.. $\endgroup$
    – A.K.
    May 23, 2014 at 14:53
  • $\begingroup$ Very likely. Also the OEIS article says it's a conjecture. $\endgroup$
    – Joni Teräväinen
    May 23, 2014 at 17:43
  • $\begingroup$ Re, what OEIS article? $\endgroup$
    – LSpice
    Aug 18, 2023 at 16:16
3
$\begingroup$

See also OEIS sequence A075555.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.