Inverting the totient function For what values of $n$ does the equation $\phi(x) = n$ have at least one solution? Is there any efficient way to check it for a given $n$?
It obviously has no solutions for odd $n$. And the smallest even number for which it has no solutions is $14$.
 A: See http://oeis.org/A002202 and further references there.
UPDATE: See also my recent paper "Computing the (number or sum of) inverses of Euler's totient and other multiplicative functions", which presents a generic algorithm for finding the inverses of a multiplicative function for a given integer value.
A: I recently answered this related question about the Carmichael function on math.SE.  The algorithm uses an unconditional lower bound so it should work just as well for the totient function because $\lambda(x) \le \phi(x)$.  My answer (the only one) has not been accepted and the question has a bounty which expires tomorrow.  I should not like to receive a bounty by default for an incorrect answer, so I am posting this here now as an invitation for you to correct me on math.SE.  It is not an efficient algorithm as this MO question demands, but I proffer it because no algorithm has yet been given to answer it.
Also related is Carmichael's totient function conjecture which is that there are no unique solutions to this equation.
