10
$\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.
    Commented 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
    Commented 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
    Commented May 24, 2014 at 10:44

2 Answers 2

Reset to default
21
$\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.
    Commented May 23, 2014 at 14:53
  • $\begingroup$ Very likely. Also the OEIS article says it's a conjecture. $\endgroup$
    – Joni Teräväinen
    Commented May 23, 2014 at 17:43
  • $\begingroup$ Re, what OEIS article? $\endgroup$
    – LSpice
    Commented Aug 18, 2023 at 16:16
3
$\begingroup$

See also OEIS sequence A075555.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .