1
$\begingroup$

Let $f(p) = \frac{2(\pi(p)-2)}{p-1}$ where $\pi$ is the prime counting function, prove that $f(p) \leq 0.6$ for all prime numbers $p \geq 31$.

Below are some examples of $f(p)$.

enter image description here

$\endgroup$
3
$\begingroup$

Well, removing multiples of $2,3,5$ between $n+1$ and $n+30$ allows you to bound $\pi(n+30)\leq \pi(n)+8$ for $n>5$, and $\frac{16}{30}<0.6$. So it remains to check $2\pi(n)-2\leq0.6\times(n-1)$ for $31\leq n\leq 60$ explicitly.

$\endgroup$
  • $\begingroup$ Thank you for yor response. I unfortunately cannot follow it. Can you provide more details? Thanks. $\endgroup$ – temp watts Jun 9 at 2:14
  • $\begingroup$ We are going to show $2(\pi(p)-2)/(p-1)<0.6$ holds for all integers $p\geq 31$, not just primes. Being nonmultiples of 2, 3 or 5 is a necessary but not sufficient condition for being a prime > 5. So $\pi(n+30)\leq\pi(n)+8$ for $n>5$ (in fact also for $n=5$ too). Check that it does give the induction step (that is what the $16/30<0.6$ is doing if you check what the induction step from $n$ to $n+30$ needs), so all you have to do is to fill in the base case(s). $\endgroup$ – user10354138 Jun 9 at 2:28
  • $\begingroup$ Thank you very much. I understand now. $\endgroup$ – temp watts Jun 10 at 15:06
1
$\begingroup$

Note that $\phi(30)=8$ so among $30$ consecutive integers only $8$ are coprime to $30$ and thus cannot be prime (unless $p=2$, $3$ or $5$). Therefore we have $\pi(n)-3 <\frac{8}{30}n$, can you finish from here?

$\endgroup$

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.