5
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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 ? $\endgroup$ – reuns Nov 18 '16 at 10:08
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Oops weird. Any idea why it would be finite ? $\endgroup$ – reuns Nov 18 '16 at 10:13
  • $\begingroup$ @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. $\endgroup$ – lhf Nov 18 '16 at 10:16
  • $\begingroup$ @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$). $\endgroup$ – emeu Nov 18 '16 at 10:32
  • $\begingroup$ I found a reference. See my edited answer. $\endgroup$ – Robert Z Nov 18 '16 at 10:34
  • $\begingroup$ 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. $\endgroup$ – reuns Nov 18 '16 at 10:39

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.