13
$\begingroup$

I stumbled upon A065377, the list of primes which can't be written in the form $p+k^2$ ($p$ prime and $k>0$ being an integer), and it's $2, 5, 13, 31, 37, 61, 127, 379, 439, 571, 829, 991, 1549, 3319, 7549$. The comments say that this list is "probably" finite with 7549 being the last entry. I cannot find any further research on this topic so I'll ask my questions here:

Why would this list be finite? (I'm assuming a proof doesn't exist due to the comment saying "probably" so a heuristic argument would be satisfactory for me)

Is there any research on this topic I've missed in my search?

Are there any conjectures that would imply that the list is finite?

$\endgroup$
2
  • 4
    $\begingroup$ "Is there any research on this topic I've missed in my search?" How can we know, if you don't list all the papers you have come across? $\endgroup$ Commented yesterday
  • 4
    $\begingroup$ The number of primes up to $n$ is, roughly, $n/\log n$. The number of squares up to $n$ is, roughly, $\sqrt n$. So the number of numbers of the form $p+k^2$, with $p$ a prime less than $n$, and $k^2$ a square less than $n$, is roughly $n^{3/2}/\log n$. $p+k^2$ is less than $2n$ which, for large $n$, is much less than $n^{3/2}/\log n$, so, heuristically, not only is every sufficiently large number the sum of a prime and a square, but the number of such representations goes to infinity with $n$. $\endgroup$ Commented yesterday

1 Answer 1

Reset to default
15
$\begingroup$

From what i can tell, this sequence is a special case of the Hardy-Littlewood Conjecture H (see https://arxiv.org/pdf/1004.0536). This conjecture states that every large integer $n$ that is not a perfect square is the sum of a prime and a square, and predicted an asymptotic formula for the number of such representations. If true, this immediately implies the list is finite.

The full conjecture remains open, but there is strong partial progress on bounding the set of exceptions (here and here). given how number theory is so connected, there's probably like 500249385 other niche conjectures that if solved would direclty imply this as well lol

The motivation for the conjecture seems to rest on a heuristic argument, where for some prime $q$ (taken to infinity), it gets increasingly many chances to be represented as $p + k^2$.

For an odd prime $q$, consider all $k$ from $1$ to $\sqrt q$. If $k$ is odd, then $q - k^2$ is even, so it can only be prime if it equals 2. If $k$ is even, then $q - k^2$ is odd and has a real chance of being prime. There are roughly $\frac{\sqrt{q}}{2}$ such even values of $k$. Each candidate $q-k^2$ is an odd number near $q$, so by the prime number theorem, it has roughly a $1\over\ln(q)$ chance of being prime (with some local correction factors). Hence, the probability that all $\frac{\sqrt q}{2}$ candidates are composite is approximately $$\left(1 − {1\over \ln (q)}\right)^{\tfrac{\sqrt q}{2}} \approx \exp\left(\frac{-\sqrt q}{2 \ln(q)}\right)$$ This probability drops incredibly fast as $q$ increases, and a back of the envelope computation with mathematica shows that the expected total number of primes in of this form beyond 7549 is roughly 3.

however, despite being convincing, the issue (at least how i interpret it) with this argument is that it assumes being prime is a random independent event, but this isn't true irl ($q − 4$, $q − 16$, $q − 36$ etc are all correlated if you will)

Number theory isn't something im particularly good at so i could be mistkaen lol so take this as a grain of salt ig

$\endgroup$
1
  • $\begingroup$ The OEIS entry suggests that there are no more up to $10^9$ so your "roughly $3$" is presumably rather less. $\endgroup$ Commented 18 hours ago

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.