How can we calculate the cardinality of the inverse of Totient function of any positive integer n ? I tried going through this paper, but I couldn't understand the procedure.
Thanks
How can we calculate the cardinality of the inverse of Totient function of any positive integer n ? I tried going through this paper, but I couldn't understand the procedure. Thanks 


I assume you are asking about $N(m)$, the number of distinct integers $n$ which satisfy $\phi(n)=m$ where $\phi$ is the Euler Totient function. There are many results regarding upper and lower bounds for the size of $N(m)$, as well as the mean and variance. In particular, Carmichael conjectured that $N(m)$ is never equal to $1$. Pomerance gave the upper bound $$N(m)\leq m\exp{(1+o(1))\log m \frac{\log \log \log m}{\log \log m}}$$ and also showed that there are infinitely many $m$ for which $$N(m)\geq m^{\frac{5}{9}}.$$ Bateman showed that $$\sum_{m\leq x} N(m)=\frac{\zeta(2)\zeta(3)}{\zeta(6)}x+O\left(xe^{c\sqrt{\log x\log \log x}}\right),$$ and we also have that $$\sum_{m\leq x} N(m)\frac{\zeta(2)\zeta(3)}{\zeta(6)}x=\Omega\left(x^\frac{5}{9}\right)$$ For more details, see the following paper of Pomerance: Popular Values of Euler's Function. 


Here is a naive attempt, which can be refined to give an upper bound on the cardinality. I will only look at the case that the inverse n is odd, the even case being mildly more complicated. So given $p$, I want to find how many odd $n$ satisfy $\phi(n)=p$. Let $p=r2^w$ with $r$ odd. To make things interesting assume $w>0$. Pick $b \geq w$ and assume $n$ has at most $b$ factors. Place the $w$ 2's in $b$ buckets. If a prime factor $q$ of $r$ is not going into a bucket, then we must put in one bucket enough to make $q1$. Otherwise, distribute the prime factors of $r$ into the buckets. Each bucket will contain those primes which multiply to form $q1$, where $q$ is a factor of $n$. If $r$ has $c$ not necessarily distinct prime factors, there are then at most $c^{b+1}$ ways to distribute the factors of $r$, and not all of them will work. A recursive version is to assume the least prime factor of $n$ is $q$, and then try to find solutions to $\phi(m)=p/[(q1)q^s]$ for appropriate values of $s$. This may be quicker to implement but harder to analyze. Gerhard "Ask Me About System Design" Paseman, 2012.10.12 


f you are interested in a computational approach, there is software that can compute $\varphi^{1}(n)$. PARI/GP Scripts for Miscellaneous Math Problems by Max Alekseyev check invphi.gp. The original invphi.gp appears for quite old pari/gp and doesn't run on current pari, I ported it here. Here is a sample session:



See also my recent paper "Computing the (number or sum of) inverses of Euler's totient and other multiplicative functions", which presents a generic dynamic programming algorithm for finding the inverses of a multiplicative function for a given integer value. Please let me know if something is unclear. 


Of course you should also take a look at This OEIS entry, and to the references within. 

