I've come up with a conjecture that seems similar in strength to Legendre's or Oppermann's, but maybe subtly different.

Let $a_n$ be the smallest nonnegative value such that there is no $m$ in $1<m<n/2$ where $n \equiv a_n \pmod m$. Then for all $n>2$, we have $n-a_n=p_{\pi(n)-1}$, the closest previous prime to $n$.

Take $n=16$ as an example:

$$\begin{eqnarray} 16 &\equiv 0 \pmod 2 \\ &\equiv 1 \pmod 3 \\ &\equiv 0 \pmod 4 \\ &\equiv 1 \pmod 5 \\ &\equiv 4 \pmod 6 \\ &\equiv 2 \pmod 7 \end{eqnarray}$$

The smallest value not seen is $a_n=3$, and $16-3=13$ is the previous prime. In cases where $n$ itself is prime, e.g. $17$ yielding the values $\{1,2,1,2,5,3,1\}$, you can either interpret $0$ as the missing value and $17$ as the prime, or $4$ giving $17-4=13$. (I'm not sure which is the more consistent interpretation.)

I've verified this empirically through $10^5$, but cannot come up with a proof. In fact, I suspect a proof would be very difficult since what this seems to come down to is whether there is always a prime in the interval $(n,n+d)$ for a composite $n$, where $d$ is the largest proper divisor of $n$. This has its worst case for forms of $p^2$, which seem to require a prime in $\left(p^2, p(p+1)\right)$.

Note that when $a_n < \lfloor \sqrt{n} \rfloor$, it is easily provably true; the problem is you can't guarantee it will be in that range, despite the fact that it almost certainly is for all $n \geq 127$.

I'm curious whether this conjecture already exists somewhere or is actually equivalent to one of the better-known prime gap conjectures. Better yet would be a proof, but that's obviously wishful thinking.

  • $\begingroup$ $\pi_n:=\vert\{p: 1<p\leq n, p\in\mathbb{P}\}\vert$ in a lot of programming languages. $\endgroup$
    – user645636
    Nov 29, 2019 at 17:30
  • $\begingroup$ You say $m <n/2$ but in the example $n=16$, you let $\max \{m\}=n/2$. Is the inequality strict or not? $\endgroup$
    – Mr Pie
    Dec 26, 2019 at 0:40
  • $\begingroup$ @MrPie Whoops, fixed. $\endgroup$
    – Trevor
    Jan 9, 2020 at 9:37

2 Answers 2


The following statements are equivalent:

$a$ is the smallest number such that $n \not\equiv a \mod 2 \dots\frac{n-1}{2}$.
$a$ is the smallest number such that $n-a \not\equiv 0 \mod 2\dots\frac{n-1}{2}$.
$a$ is the smallest number such that $n-a$ is not divisible by $2\dots\frac{n-1}{2}$.
$a$ is the smallest number such that $n-a$ is prime.
$n-a$ is the largest prime below $n$.


It's incredibly simple. Every composite needs a factor at most half of itself (more accurately its square root). It follows that since half of $n$ is greater than half of anything below it, any composite below it will have to have a divisor in the range. The fact you can't shift down any remainder to hit 0 for that number, shows it's prime.

Using the sqrt method, remembering $$m\equiv 0\bmod m$$ we can use $$16\equiv 2\bmod 2$$$$16\equiv 1\bmod 3$$$$\implies 2,3\nmid 16-3$$ and be done. We also only need to check prime moduli.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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