Find all values of N that satisfy ϕ(N) = x for any given x value How would I determine all values of n in ϕ(n) = x for any value of x where ϕ is Euler's totient function? (and -1 if x is not a totient). Is there a simple formula for this? Or is this a lot more complicated than I think this is? Simply trying every number from x + 1 to the upper limit is too inefficient. I will be using numbers up to 1,000,000,000,000, so efficiency is key here.

The paper below proves that it is very unlikely that this problem can be solved efficiently:

"Complexity of Inverting the Euler Function" by Scott Contini, Ernie Croot and Igor E. Shparlinski, published in Mathematics of Computation (doi, arxiv)

