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.

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.

share|improve this question
    
My apologies if I am missing something basic here, but what function is it that you are defining to mean $\varphi(x)$? –  Amzoti Dec 26 '12 at 18:31
    
Euler totient function.. phi(x)... gives the number of integers less than x which are coprime to x –  Purva Gupta Dec 26 '12 at 18:35
    
So I don't waste time, you are asking for an efficient algorithm for inverting the Euler Totient function. Correct? –  Amzoti Dec 26 '12 at 19:26
    
yes.. which can work for large test cases –  Purva Gupta Dec 26 '12 at 19:48
1  
I would recommend changing your title to be more descriptive in case others are searching for this too and there have been previous questions regarding approaches. Regards –  Amzoti Dec 27 '12 at 2:19

2 Answers 2

up vote 11 down vote accepted

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

share|improve this answer
    
Thanks a lot for your descriptive answer :) –  Purva Gupta Dec 27 '12 at 8:19
    
@Purva Gupta, you are very welcome! We are all here to learn from each other and MSE is a wonderful site! –  Amzoti Dec 27 '12 at 9:01
    
2∗3^(L−1) is it applicable for all or only specific numbers? –  Purva Gupta Dec 27 '12 at 9:18
    
All, it is an upper bound using this method for the largest n, recalling that n must be even numbers only from the note. –  Amzoti Dec 27 '12 at 13:08
    
$+1^{+1^{+1}}\quad\checkmark$ –  amWhy May 10 '13 at 1:20

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.

share|improve this answer

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.