Project Euler Solution 69: Totient maximum

Project Euler Problem 69: Totient maximum introduces Euler's totient function and requires us to learn a bit about it in order to solve the problem.

Euler's Totient function, $\phi(n)$ (sometimes called the phi function), is defined as the number of positive integers not exceeding $n$ which are relatively prime to $n$. For example, as 1, 2, 4, 5, 7, and 8, are all less than or equal to nine and relatively prime to nine, $\phi(9) = 6$.

$n$	Relatively Prime	$\phi(n)$	$n/\phi(n)$
2	1	1	2
3	1, 2	2	1.5
4	1, 3	2	2
5	1, 2, 3, 4	4	1.25
6	1, 5	2	3
7	1, 2, 3, 4, 5, 6	6	1.1666…
8	1, 3, 5, 7	4	2
9	1, 2, 4, 5, 7, 8	6	1.5
10	1, 3, 7, 9	4	2.5

It can be seen that $n=6$ produces a maximum $n/\phi(n)$ for $n \leq 10$.

Find the value of $n \leqq 1\,000\,000$ for which $n/\phi(n)$ is a maximum.

It seems that we first have to write an implementation for the totient function. And for that we need to determine which numbers are relatively prime to each other. This can for instance be done by using our prime factor function from an earlier solution and check whether numbers have common prime factors. To compute $\phi(n)$, we go through all $k < n$ and check whether they have common prime factors. A slightly better way to do the same is just using the greatest common denominator (GCD). Numbers which are relatively prime has a GCD of 1.

The problem with checking all $k < n$ for all $n$ is that this already sets us up for an algorithm with $O(n^2)$ at least. The GCD check likely also scales with $n$. Given the large $n$, we will quickly have a problem. One can do this, but it will take several hours to do so.

Special functions have many interesting properties, therefore it makes sense to take a look at the Wikipedia article about the totient function. There we find an interesting representation of this function. Any number can be written as a product of its prime factors $p_i$ and their multiplicity $k_i$ like this: $$ n = \prod_i p_i^{k_i} \,. $$

The totient function for that number can be written as $$ \phi(n) = \prod_i p_i^{k_i - 1} (p_i - 1) \,. $$

This then allows us to write the desired quotient as the following: $$ \frac{n}{\phi(n)} = \prod_i \frac{p_i}{p_i - 1} \,. $$

We want to maximize this expression. We can see that since $p_i > 1$, the fractions $\frac{p_i}{p_i - 1}$ are always greater than 1. The factors are largest if $p_i$ is smallest. And each prime factor only gives one factor, repeating the same prime factor doesn't increase the value of $\frac{n}{\phi(n)}$.

That means that in order to maximize $\frac{n}{\phi(n)}$ we have to get as many prime factors as possible, and these factors shall be as small as possible. Therefore the desired solution is just the product of the smallest prime factors which is below the given ceiling.

The result is very simple, we use the prime generator from Solution 3: Largest prime factor and muliply them together until we reach the ceiling.

def solution() -> int:
    ceiling = 1000000
    result = 1
    for prime in prime_generator():
        if result * prime > ceiling:
            return result
        result *= prime

This produces the result in 2 µs.

In this problem we have seen that sometimes looking at the special properties of a function really helps us to see a solution that is hard to impossible to compute with brute force. This learning is what Project Euler is all about. And this problem has helped me learn a bit more, so that's great!