Inverse Totient Procedure

When I have time, I enjoy solving the problems at Project Euler. I have solved 177 problems as of today using R as my primary tool. In fact, I found Project Euler when I was looking for problems I could use to learn R. At one point I was third ranked by problems solved in the R listings, but I have since slipped to sixth – the takeaway is that the R-crew are not the cream of the crop on Project Euler!

Leonhard Euler came up with the Totient function (the Totient of n is the number of integers less than n coprime to n). Not surprisingly, totients feature in a number of the Project Euler problems. One I have been struggling with involves inverting the totient function. This is not straightforward because for any given totient, there are at least two numbers that could have given rise to it. For example, 3, 4, and 6 all have a totient of 2 (1,2 are coprime to 3; 1, 3 are coprime to 4; 1, 5 are coprime to 6).

I have searched all the usual places for a procedure to invert the totient function. I found answers to specific questions (i.e. if the totient of n is 1000 what is n?). I found academic papers that provide procedures, but I couldn’t find a nice simple recipe. So based on what I found, here’s one …

To find all the possible numbers, n, that have the totient value, m, implement the following procedures:

The Basic Idea

Given “m” we are solving the following for “n”:

We can also factor m:

So we have to find solutions that allow all the prime factors to “line up”. For example, a prime, q, can appear in the factorization of m even though it doesn’t appear as a factor of n if it is a factor of one of the numbers (p – 1)!

The recipe depends upon solving the problem above for smaller values of m. e.g to solve for m = 12, requires solving for m = 1, 2, and 6. Depending on the nature of the problem you are solving, either start from the knowledge that Phi(1) = Phi(2) = 1 and work up the totient “chain”, or implement the procedure recursively, working down the totient chain.

We can attack the problem along two paths, one via the (p – 1)’s and the other via the p^e‘s.

The (p_i – 1) Attack

1. List all the primes greater than 2 up to m + 1, let’s call this list p_i
2. For each p_i divide m by (p_i – 1), discard any results that are not even integers or 1. Let’s call these Phi_i.
3. For each Phi_i, look up k_{i, j}, the integers whose totients are Phi_i. Only retain those that are coprime to p_i.
4. n = k_{i, j}.p_i. This arises from the fact that Phi(x.y) = Phi(x).Phi(y) x, y coprime.
5. Eliminate duplicate n.

The p_i^e_i Attack

1. Factorize m.
2. For each prime factor of m, q_i, calculate . Retain only even integers and 1. Let’s call these Phi_i.
3. For each Phi_i, look up k_{i, j}, the integers whose totients are Phi_i. Only retain those that are coprime to q_i.
4. n = k_{i, j}.q_i^{f_i + 1}

Bringing It Together

This bit is simple: de-duplicate the answers figured out in the two methods above.

I still have to ensure this is correct by figuring out all the numbers less than 40 million that give rise to totient chains with exactly 25 steps per the Project Euler question. I will confirm when done.

EDIT: Well, it works as far as I can tell. Of course, it turns out not to be the way to solve the specific problem which would have been obvious if I just considered how long it would take to do 2^25 factorizations. Duh.

In R, with some judicious vectorizing, it turns out to be much quicker just to calculate the totients of every number between 1 and 40,000,000 using a sort of sieving process (~7s on my machine). Then one can find any chain of any desired length with any additional constraints your heart desires!