Define $\psi(n)=\pi(n)-\phi(n)$ where we have the prime counting function and totient function respectively.

I'm interested in where $\psi(n)=0$.

Specifically is it possible to prove that there are exactly $9$ roots, namely for $n=0,2,3,4,8,10,14,20,90$. I calculated these roots but I couldn't find any more.

I think this function has finitely many roots because the totient function grows faster and thus becomes greater than the prime counting function at a certain threshold.

Thanks for your help. I'm not sure how simple or how difficult this is to prove, and I appreciate any ideas and hints.

  • $\begingroup$ Indeed, the ratio explodes and tells you that there are only finitely many solutions. On wikipedia you find upper and lower bounds for those two functions. I would give it a try to see what kind of threshold you get. $\endgroup$ – Severin Schraven Apr 22 at 0:51

yes, Rosser and Schoenfeld showed (formulas 3.41 and 3.42) that $\phi$ (which is, on average, linear) is never much worse than that: namely $$ \phi(n) \geq \frac{n}{e^\gamma \log \log n + \frac{2.50637}{\log \log n}} $$ Here the logarithm is base $e$ and the constant $2.50637$ chosen to give equality at (and only at) $$ n = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 23 = 223092870 $$

There are also upper bounds on $\pi(x),$ for example formula 3.2.


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.