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 '19 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 '19 at 0:40
  • $\begingroup$ @MrPie Whoops, fixed. $\endgroup$ – Trevor Jan 9 at 9:37

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

| cite | improve this answer | |
  • $\begingroup$ Without looking too closely, that seems like it can't be quite right. IIRC, this conjecture is true only if for all prime $p$ there's a prime $q$ where $p^2<q<p^2+p$, which is a long-open question. If I'm not mistaken, and if $a$ as I described it is equivalent to your statements here, that would settle that question, which is terribly unlikely. $\endgroup$ – Trevor Jan 9 at 11:54

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.

| cite | improve this answer | |

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.