3
$\begingroup$

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?

  • 0
    @GerryMyerson: I just need the smooth version, the much harder question solved at A139795 is too computationally intensive for my needs.2012-07-18

1 Answers 1

1

Assume we're going to find a bound of the form $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) 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$.