inversion of the Euler totient function

Question

Given an integer $n$ find smallest integer $x$ such that $\varphi(x) = n$.

$$10^5 < n < 10^8$$

I know that lower bound for searching is $n+1$ and the upper bound is

$$\frac{n}{e^{0.577}\log(\log(n))} + \frac{3}{\log(\log(n))}$$

But my problem is that for such a large values of $n$ my program with precomputed $\varphi(x)$ values has to do a lot of searching and is highly inefficient.

Can you please provide any other method for doing the same .

Thanks.

Answer 1

Warning, you are going to have to do some work to get your hands around this answer, but I provided enough details for you to work through it and it answers your question.

Goal: Given an integer $n$ find the smallest integer $x$ such that $\varphi(x) = n$.

Approach

One can calculate all of the possible integers with a totient of $n$ using "Inverse Totient Trees."

For instance, take the integers with a totient of $24$. Then,

$\varphi(N) = 24$

$\varphi(24) = 8$

$\varphi(8) = 4$

$\varphi(4) = 2$

$\varphi(2) = 1$

There are $5$ "links" (designate this as $L$) in the totient chain so to speak, with $4$ intervals. In general, the greatest integer that can have a totient of $n$ is $2*3^{(L-1)}$, which means that $2*3^{(5 - 1)}$ $= 162$ is the upper bound of an integer with a totient of $24$.

In fact, via a simple proof by exhaustion, one can easily check a table and see that the smallest integer where $\varphi(x) = 24$ is $x = 35$ (see the list below).

$$\varphi(x)= n = 24 \rightarrow x = 35, 39, 45, 52, 56, 70, 72, 78, 84, 90$$

Here are a couple of related number sequences which include references for you to investigate this approach.

A032447 Inverse function of phi( )

A058811 Number of terms on the n-th level of the Inverse-Totient-Tree (ITT)

So, the next obvious question, is there a program that is related or tangentially related that can generate all of those values in the range specified using some approach?

Yes, see Solving $\varphi^{-1}(x) = n$, where $\varphi(x) = n$ is Euler's totient function - testing Carmichael's conjecture. Please see the references there for further details on this program - including the C-source code.

Lets do the example above and the some examples within your range (note that numbers are obviously never odd because $\varphi(x)$ is always even for $n \ge 3$).

$n = 24$: Enter $n = 24, e = 0, f = 0$: and look at the resulting $10$-bolded numbers and compare that list to the above. If you sort that list from low to high, it is all of the $x's$ that produce that desired $n$. Of course, you only want the minimal (last bolded number in the display) one. So $\varphi^{-1}(35) = 24$.

$n = 10^{5}$: Enter $n = 100000, e = 0, f = 0$: see the metrics for how many numbers satisfy this, but your desired result is $x = 100651$.

$n = 10^5 + 1$: Enter $n = 100001, e = 0, f = 0$: Odd numbers are not permissible by statement above.

$n = 10^{5} + 2$: Enter $n = 100002, e = 0, f = 0$: see the metrics for how many numbers satisfy this, but your desired result is $x = 100003$.

$n = 5*10^{5}$: Enter $n = 500000, e = 0, f = 0$: see the metrics for how many numbers satisfy this, but your desired result is $x = 640625$.

...

$n = 10^{8}$: Enter $n = 100000000, e = 0, f = 0$: see the metrics for how many numbers satisfy this, but your desired result is $x = 100064101$.

Asides

This is a very interesting problem and has been asked before, so I am summarizing some of the other discussions and references I found in case others want to consider more approaches.

There are several papers on the topic of finding the inverse of the Euler Totient function:

Euler's Totient Function and Its Inverse, by Hansraj Gupta

The number of solutions of $\phi(x) = m$, by Kevin Ford

On the image of Euler’s totient function, R.Coleman

Complexity of Inverting the Euler Function, by Scott Contini, Ernie Croot, Igor Shparlinski

There have been several questions along these lines, for example, the-inverse-of-the-euler-totient-function, inverting-the-totient-function and finding-the-maximum-number-with-a-certain-eulers-totient-value

There are some other code examples that use different methods for you to consider, see, for example:

Inversion of Euler Totient Function by Max Alekseyev and you can experiment with this since PARI/GP is free. Play around with the function and see if you can modify your approach with this approach.

Discussion and implementation of an efficient algorithm for finding all the solutions to the equation EulerPhi[n] = m, by Maxim Rytin is a nice article off of wolfram that gives an efficient algorithm for computing the inverse of the Euler totient function. Download the invphi.nb file at the bottom and get Mathreader. As an alternative, you can see oeis A006511.

MAGMA - see FactoredEulerPhiInverse(n)

Regards

Answer 2

See also my recent paper "Computing the (number 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.

Answer 3

I made an efficent java implementation of the Inverse Euler Totient (invphi) using the algorithm described by Hansraj Gutpa. It also uses the fastest factorization implemented in java since factorization is one of the bottlenecks.

See: https://github.com/thomasegense/bigmathfast