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

  • 0
    Than$k$s -- one of the lin$k$s from that question coul$d$ be adapted to solve this problem reasonably efficiently.2011-06-03
1

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

  • 0
    Good point. I did give you a +1 for your effort...2011-06-03