3
$\begingroup$

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

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

  • 0
    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: http://mathoverflow.net/questions/3274/how-hard-is-it-to-compute-the-euler-totient-function2011-06-03
  • 0
    @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.2011-06-03
  • 0
    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.2011-06-03
  • 0
    ok, sorry, I misread.2011-06-03

2 Answers 2

1

This seems to be a hard problem. See https://mathoverflow.net/questions/31691/inverting-the-totient-function (but that post is about inverting $\phi$, not deciding whether there is a solution).

  • 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.2011-06-03
  • 0
    Thanks -- one of the links from that question could be adapted to solve this problem reasonably efficiently.2011-06-03
1

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

  • 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.2011-06-03
  • 0
    "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.2011-06-03
  • 0
    Good point. I did give you a +1 for your effort...2011-06-03