# Minimal $x$ for which $\phi(k) > n$ for all $k > x$

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?

-
Would you mind and tell up what $\varphi$ is? –  Dirk Jul 17 '12 at 15:35
Euler's totient function, oeis.org/A000010. –  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 oeis.org/A139795 but no estimates are given. It is closely related to oeis.org/A137315 and maybe the references at that sequence would be helpful. –  Gerry Myerson Jul 18 '12 at 1:17
show 1 more comment

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$.