Using this lemma it can be proved that $\Delta(m,n)=\pi(m\cdot n)-\pi(m)\cdot\pi(n)+1$ (where $\pi$ is the prime counting function) is a function $\Delta:\mathbb N\times\mathbb N\to\mathbb N$.

Reformulated conjecture:

Given $m\in\mathbb N,m>2$, then $n\in \mathbb N$ is an odd prime if $\Delta(m,n-1)>\Delta(m,n)<\Delta(m,n+1)$ and if $n$ is an odd prime then $\Delta(m,n-1)\ge\Delta(m,n)\le\Delta(m,n+1)$.

The conjecture is tested for $m,n<3000$.

Counterexample: $5879$ is a prime, but $\Delta(5878,5879)=1525672>\Delta(5878,5878)=1523414$

  • 3
    $\begingroup$ $\Delta(3,11)=\Delta(3,12)$. $\endgroup$ – Wojowu Dec 28 '15 at 17:55
  • $\begingroup$ Thanks @Wojowu, I should have tested it better! I might reformulate. $\endgroup$ – Lehs Dec 28 '15 at 18:00

Suppose $\Delta(m,n-1)>\Delta(m,n)$, then $$\pi(mn-m)-\pi(m)\pi(n-1)+1>\pi(mn)-\pi(m)\pi(n)+1\\\pi(m)\pi(n)-\pi(m)\pi(n-1)>\pi(mn)-\pi(mn-m)\geq 0\\\pi(n)>\pi(n-1)$$ so $n$ must be prime, since $\pi(x)$ increases on $n$.

If $n$ is prime, then $\pi(n)=\pi(n-1)+1$, so we can transform $\Delta(m,n-1)\geq\Delta(m,n)$ as follows: $$\pi(mn-m)-\pi(m)\pi(n-1)+1\geq\pi(mn)-\pi(m)\pi(n)+1\\ \pi(m)\pi(n)-\pi(m)\pi(n-1)\geq\pi(mn)-\pi(mn-m)\\ \pi(m)\geq\pi(mn)-\pi(mn-m)$$ This is equivalent to specific cases of second Hardy-Littlewood conjecture. Obviously we don't get full generality, but nevertheless I seriously doubt anything is known on this. Even though the mentioned conjecture is believed to be false, this special case might just as well be true.

Lastly, if $n$ is odd prime, then $n+1$ isn't, so $\pi(n+1)=\pi(n)$, so transforming $\Delta(m,n+1)\geq\Delta(m,n)$ we easily get $$\pi(mn+m)\geq\pi(mn)$$ which is clearly true.

To sum up:

First part of your conjecture is true. Indeed, already $\Delta(m,n-1)>\Delta(m,n)$ implies $n$ is prime.

Primality of $n$ implies $\Delta(m,n+1)\geq\Delta(m,n)$, but whether it implies $\Delta(m,n-1)\geq\Delta(m,n)$ is most likely an open problem.

  • $\begingroup$ I really like the way you solve this kind of problems... $\endgroup$ – Lehs Dec 28 '15 at 21:59
  • 1
    $\begingroup$ @Lehs What do you mean? I have just unraveled the definition of $\Delta$ and made some elementary transformations. $\endgroup$ – Wojowu Dec 28 '15 at 22:46
  • 2
    $\begingroup$ It's easy when it's done. But I never was a good problem solver and now a days I'm rusty and lazy... But, it's never too late to learn and develop. $\endgroup$ – Lehs Dec 28 '15 at 22:51

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.