Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

It's well-known that $$ \liminf_n\frac{\varphi(n)\log\log n}{n}=e^{-\gamma} $$ and there exists an effective version $$ \varphi(n)>\frac {n}{e^\gamma\log\log n+\frac{3}{\log\log n}} $$ valid for $n\ge3.$ Of course the RHS is increasing and so has an inverse, but I would like to know if there is an explicit formula (giving a tight bound) with $$ \varphi(f(n))>n. $$

Is this too much to ask?

share|cite|improve this question
Would you mind and tell up what $\varphi$ is? – Dirk Jul 17 '12 at 15:35
Euler's totient function, – Charles Jul 17 '12 at 15:36
Are you asking whether there is readily available (non-asymptotic) inverse bound? Or are you looking for something tighter than what can be extracted from the lower bound on $\phi(n)$? – Erick Wong Jul 17 '12 at 18:06
@ErickWong: Something more explicit than "the inverse of n/(e^gamma ...)" but hopefully not much weaker than that. Something that's asymptotically the right size, at least -- $e^\gamma n\log\log n.$ – Charles Jul 17 '12 at 18:57
The function is tabulated at but no estimates are given. It is closely related to and maybe the references at that sequence would be helpful. – Gerry Myerson Jul 18 '12 at 1:17
up vote 1 down vote accepted

Assume we're going to find a bound of the form $n<f(n) < n\log n$ (at least for $n$ large enough) so $$ \begin{align} \log n < \log f & < \log n+\log\log n\\ \log\log n < \log \log f & < \log(\log n + \log\log n)\\ \end{align} $$ Then from your bound $\phi(f)<n$ requires that $$ f < n \left(e^\gamma\log\log f+3/\log\log f\right) \\ f < n \log\log f (e^\gamma+3/(\log\log f)^2) \\ f < n\log(\log n + \log\log n)\left(e^\gamma+3/(\log\log n)^2\right) $$ So $$ N>n\log(\log n + \log\log n)\left(e^\gamma+3/(\log\log n)^2\right) \Rightarrow \phi(N)>n $$ I guess there may be a slightly better version, since the bound for $n=10^7$ gives $6.38\times 10^7$, whereas the last $N$ with $\phi(N)\le 10^7$ seems to be $58198540$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.