Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

2 Answers 2

up vote 1 down vote accepted

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).

share|improve this answer
1  
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
    
Thanks -- one of the links from that question could be adapted to solve this problem reasonably efficiently. –  Charles Jun 3 '11 at 3:28

There are many references to track down at http://oeis.org/A005277

share|improve this answer
1  
I read the sequences and all the references there before posting. There are really only two references: Guy's UPNT and Ford-Konyagin-Pomerance. Havelock is elementary, EIS is a proper subset of the information on the OEIS, Weisstein and Wikipedia have nothing to say. –  Charles Jun 3 '11 at 3:07
    
"I read the sequences and all the references there before posting." Well, then maybe you could have mentioned that in your question, and saved me the effort of trying to help you. –  Gerry Myerson Jun 3 '11 at 4:48
    
Good point. I did give you a +1 for your effort... –  Charles Jun 3 '11 at 19:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.