# How many solutions do exist for $\varphi(n)=\pi(n), n\in\mathbb{N}$?

How many solutions do for the following equation exists?

\begin{align} \varphi(n)=\pi(n), n\in\mathbb{N}, \end{align}

where $\varphi(n)$ is Euler's totient function and $\pi(n)$ is the prime-counting function.

Thank you very much

• Do you know the probabilistic model for the prime numbers, serving as a heuristic justification of the Riemann hypothesis the twin primes and the Goldbach conjecture and almost every conjecture on the prime numbers ? What would be the answer of your question under this model ? – reuns Nov 18 '16 at 10:08

Surprisingly, the list of solutions is finite: 2, 3, 4, 8, 10, 14, 20, 90. Moreover $\varphi(n)>\pi(n)$ for $n>90$.

A proof is given at page 179 in the following paper by Leo Moser: "On the equation $\varphi(n)=\pi(n)$", Pi Mu Epsilon J. 1951, 177–180.

Sketch of Moser's proof. We have that $\varphi(n)-\pi(n)=B(n) - A(n)$ where $A(n)$ is the number of prime divisors of $n$ and $B(n)$ is the number of non-primes, which do not exceed $n$ and are relatively prime to $n$.

Now i) $\pi(\sqrt{n})\geq 2A(n)$ for $n>360$ (lemma 3 where Bertrand's postulate is used) and ii) $B(n)>\pi(\sqrt{n})-A(n)$ (lemma 4).

Hence by for $n>360$, $$\varphi(n)-\pi(n)=B(n) - A(n)>\pi(\sqrt{n})-A(n)-A(n)\geq 0.$$

P.S. According http://oeis.org/A037171, the result has been proved by David W. Wilson and Jeffrey Shallit, but unfortunately no reference is provided.

• Oops weird. Any idea why it would be finite ? – reuns Nov 18 '16 at 10:13
• @user1952009, $\phi(n) \sim n$ and $\pi(n) \sim n/\log n$ and so $\phi(n)$ should eventually overcome $\pi(n)$. This is not a proof, though. – lhf Nov 18 '16 at 10:16
• @lhf I believe that it is actually a proof that the list must be finite: $\forall \varepsilon>0, \exists N\in\mathbb N, \forall n\geq N, 1-\varepsilon < \pi(n)\log(n)/\phi(n) < 1+\varepsilon$, which implies that the list must be finite (specialize for instance $\varepsilon$ to $0.01$). – emeu Nov 18 '16 at 10:32
• I found a reference. See my edited answer. – Robert Z Nov 18 '16 at 10:34
• Let $N_x = \prod_{p < x} p$ the primorial. The Mertens theorem gives $\lim \sup_x \ln (x) \frac{\phi(N_x)}{N_x} = e^{-\gamma}$. Now $\ln N_x \sim x$ so that $\lim \sup_n\ln \ln n\frac{\phi(n)}{n} = e^{-\gamma}$ and $\frac{\phi(n)}{n} < \frac{C}{\ln n}$ is finite. – reuns Nov 18 '16 at 10:39