From the fact you're citing, it looks like

$$ f(n) = \max \{ m : \Phi(m) \le n \}. $$

For example, $\Phi(30) = 7$ and $\Phi(m) \ge 11$ for all $m \ge 31$ (note that since $\phi(n) \ge \sqrt{n}$ we only need to check finitely many values!) -- so $f(7) = f(8) = f(9) = f(10) = 30$.

Now, consider the fact that
$$ \lim \inf \phi(n) {\log \log n \over n} = e^{-\gamma} $$
which is equation (20) in this Mathworld article. Of course this holds if we replace $\phi$ by $\Phi$.

So $f(n)$ should grow like the inverse of the function
$$ n \to {e^{-\gamma} n \over \log \log n} $$. It appears, then, that $f(n) \sim e^\gamma n \log \log n$ as $n \to \infty$.

Unfortunately this disagrees with your estimate. One of us is wrong somewhere.

**EDIT**: I believe my argument is basically right, but the original fact was stated incorrectly. From the paper of Levitt that Stanley pointed to, we should actually have

$$ \Phi( p_1^{\alpha_1} \cdots p_k^{\alpha_k}) = \phi(p_1^{\alpha_1}) + \cdots + \phi(p_k^{\alpha_k}) - [k \equiv 2 \mod 4] $$

and so $\Phi(x)$ is usually much smaller than $\phi(x)$ -- therefore $f$ grows much faster than I said it did.

`$\Phi(m)$`

when $m$ is odd or a multiple of 4? Both branches of the definition seem to apply in these cases. And your resultalreadyis about asymptotic behaviour of $f(n)$. I suppose you want a better estimate? Can you indicate how good an estimate you need? – Harald Hanche-Olsen Feb 12 '10 at 15:23