Project Euler Solution 70: Totient permutation

Project Euler Problem 70: Totient permutation continues with the totient function.

Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine the number of positive numbers less than or equal to n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6. The number 1 is considered to be relatively prime to every positive number, so φ(1)=1.

Interestingly, φ(87109)=79180, and it can be seen that 87109 is a permutation of 79180.

Find the value of n, 1 < n < 107, for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum.

This feels like a direct continuation of Problem 69: Totient maximum. The stark difference is that we look for a minimum here whereas in Problem 69 we have looked for a maximum of the expression $n/\phi(n)$.

In the previous post we have learned that the ratio $n/\phi(n)$ can be written like this: $$ \frac{n}{\phi(n)} = \prod_i \frac{p_i}{p_i - 1} \,. $$

We can see that each factor is greater than one. If we are to maximize this, we need to take as many small prime factors as we can. If we take a look at the numbers for $n < 1\,000$ and create a table sorted by maximal value of $n/\phi(n)$, we get these numbers consisting of small primes:

We are interested in the other thing now. We want to have the fewest factors and with the largest primes. Sorting the table the other way around shows that indeed the largest primes have the smallest $n/\phi(n)$:

The problem with primes is that their totient is just one less than the prime, namely $\phi(p) = p - 1$. But that means that the $p$ and $\phi(p)$ cannot be digit permutations of each other. We need to have a product of at least two primes to get somesomething of interest.

We can filter the table to only include numbers such that the number and its totient are digit permutations. We also increase the ceiling to 100,000 such that we get more interesting results. These are the minimum numbers that we get:

We can see that we need at least two factors. And the one with minimal $n/\phi(n)$ has two rather large prime factors. The other ones still have pretty large prime factors. When we get down to the point where we have 5 as a prime factor, the ratio $n/\phi(n)$ is already pretty large with above 1.25.

It seems likely that the desired answer $n$ is the product of two prime numbers. It could be that it is a product of three primes, but let us persue the hypothesis that it is a product of two largish primes.

We can then look at all products of primes $p_1 p_2$ where $p_i < 10\,000$. We obtain the following top 15 entries:

Unsurisingly these are the same numbers that we have found before. The problem is that with a ceiling of 10,000, this already takes 2.8 s to compute. The search scales roughly quadratically with the ceiling. So going up to the required 10,000,000 means another factor 1,000 more prime numbers and therefore 1,000,000 more compute time. It would take several months to finish, so this cannot be it.

We can save a bit of time by using that we already know the prime factors. Then we don't have to factorize the number again to compute the totient function. This brings the time down to 47 ms for this table.

There is another insight that we can use. Although the ceiling is 10,000,000, we don't need prime numbers that high. Since we want both prime numbers of the same order of magnitude, it is sufficient to only look at primes that are up to 10,000. This means that we just need to add a factor of 10 to the primes and this increases computation cost only a bit.

We then get this table:

And it turns out that the top entry is already the solution that we were looking for. The number consists of two large primes.

So what is left in the code is just a function that checks for permutations using sort_digits from Solution 62: Cubic permutations

def are_permutations(left: int, right: int) -> bool:
    return sort_digits(left) == sort_digits(right)

And then the main function goes through the primes which are generated with the prime sieve from Solution 7: 10001st prime:

def solution() -> int:
    primes = prime_sieve(10**5)
    values = []
    for p1 in primes:
        for p2 in primes:
            if p1 == p2:
                break
            number = p1 * p2
            if number > 10**7:
                break
            t = (p1 - 1) * (p2 - 1)
            if are_permutations(t, number):
                values.append((number / t, number))
    return min(values)[1]

It took 754 ms to compute, which is fine.