# Search limit for even nontotients

n is an even nontotient if n is even and Euler phi(m) = n has no solution. I am looking for a search limit L(n) depending on n. By this I mean:

If for all k, 1 <= k <= L(n) phi(k) = n has no solution then phi(m) = n has no solution.

Is there a provable limit? (My conjecture: L(n) = 2n is sufficient.)

-

The question in essence asks about a tight lower bound on the $\varphi$-function.
I believe that the best more or less universal bound is that for $n>2$, $$\varphi(n)> \frac{n}{e^\gamma \log(\log n) +\frac{3}{\log(\log n)}}$$ where $\gamma$ is the Euler-Mascheroni constant. The term $3/(\log(\log n))$ is there to take care of smallish $n$, and could be almost removed for large numbers, but I do not know the details.
However, crucially for your question, the term $e^\gamma \log(\log n)$ cannot be improved on.
If we look at how knowledge about the bound affects your problem, we can see that $\varphi(2n)$ can be significantly smaller than $n$ for huge $n$, so a search up to $2n$ would not be enough to rule out the existence of a solution of $\varphi(x)=n$.
The function $\log(\log n)$ grows exceedingly slowly. If you know roughly the range of values over which the search will take place, you can use the known bounds to find a suitable constant $c$ that enables you to replace $2n$ by $cn$.