# Deciding whether a given number is a totient or nontotient

The following algorithm decides if a number $n>0$ is a totient or a nontotient:

if n = 1
return true
if n is odd
return false
for k in n..n^2
if φ(k) = n
return true
return false


This is very slow; even using a sieve it takes $n^2$ steps to decide that $n$ is nontotient. Is there a fast method? Polynomial (in $\log n$) would be best but is probably too much to hope for.

Edit: I was able to adapt this

totient(n,m=1)={
my(k,p);
if(n<2,return(n==1));
if(n%2,return(0));
fordiv(n,d,
if(d<m|!isprime(p=d+1),next);
k=n\d;
while(1,
if(totient(k,p), return(1));
if(k%p,break);
k\=p
)
);
0
};


from Max Alekseyev's $\varphi^{-1}$ script, which is substantially faster than the pseudocode above.

-
Why are you worried about how many steps it takes and not about how long it takes to compute all those totients? AFAIK, the only method is factoring: mathoverflow.net/questions/3274/… –  lhf Jun 3 '11 at 3:31
@lhf: Where do you get that idea? I mentioned the difficulty of factoring in the original question, along with the best (worst-case) approach to factoring for that algorithm. I haven't ignored it anywhere -- in fact I'm rather concerned with it. –  Charles Jun 3 '11 at 3:35
Of course the focus of my question is on this function and not on factoring in general; it suffices to find solutions requiring the least amount of work (presumably, this is primarily factorization). The actual factoring algorithms used will be standard. –  Charles Jun 3 '11 at 3:38
ok, sorry, I misread. –  lhf Jun 3 '11 at 5:01

This seems to be a hard problem. See http://mathoverflow.net/questions/31691/inverting-the-totient-function (but that post is about inverting $\phi$, not deciding whether there is a solution).
The paper by Igor Shparlinsky referred to in the above link shows that under the Hardy Littlewood prime k-tuple conjecture and P$\neq$NP the problem of deciding if there is a solution cannot be solved in time polynomial in log n. –  David Marquis Jun 3 '11 at 2:48