I wrote about Euler’s Totient function in here, but to recap, given an integer \(n\), the Totient function \(\phi(n)\) is the number of positive integers not exceeding \(n\) and are relatively prime to \(n\). The goal of this problem is to find \(n\) such that \(\frac{n}{\phi(n)}\) is maximized.

Solution

To start, we should definitely make use of the existing formula to compute the Totient function. Given an integer \(n\) and the distinct prime divisors of \(n\), \(\{p_1,p_2...,p_k\}\), we can compute the Totient function as follows

$$ \begin{align*} \phi(n) = n \prod_{i=1}^{k} \big( 1 - \frac{1}{p_i} \big). \end{align*} $$

Since we’re interested in computing specifically \(\frac{n}{\phi(n)}\) so we get a simplified expression as follows

$$ \begin{align*} \frac{n}{\phi(n)} &= \frac{n}{n\prod_{i=1}^{k} \big( 1 - \frac{1}{p_i} \big)} \\ &= \frac{1}{\big( 1 - \frac{1}{p_1} \big) \big( 1 - \frac{1}{p_2} \big) ... \big( 1 - \frac{1}{p_k} \big)} \\ &= \frac{1}{\big( \frac{p_1 - 1}{p_1} \big) \big( \frac{p_2 - 1}{p_2} \big) ... \big( \frac{p_k - 1}{p_k} \big)} \\ &= \frac{p_1 p_2 ... p_k}{ (p_1 - 1) (p_2 - 1) ... (p_k - 1) } \end{align*} $$

Before we can implement the function, we need to generate these distinct prime factors. We implemented this before in Problem 3.

void prime_factorization(int n, std::set<int>& factors) {
    // prime factor 2
    while (n % 2 == 0) {
        n /= 2;
        factors.insert(2);
    }
    // all the other prime factors
    int limit = sqrt(n);
    for (int i = 3; i <= limit; i += 2) {
        while (n % i == 0) {
            factors.insert(i);
            n /= i;
        }
    }
    // n is prime itself
    if (n > 2) {
        factors.insert(n);
    }
}


Once we have these distinct factors, we can just run this for all integers \(n \leq 1000000\) as follows:

double max = 0.0;
int n = 0;
for (int i = 1000000; i > 0; i--) {
    if (!prime[i]) {
        std::set<int> factors;
        prime_factorization(i, factors);
        double tot = 1;
        //printf("%d: ", i);
        for (auto e = factors.begin(); e != factors.end(); e++) {
                //printf("%d, ", *e);
            tot *= *e / (*e - 1.0);
        }
        if (tot > max) {
            max = tot;
            n = i;
        }
        //printf("tot = %f \n", tot);
    }
}
printf("max n = %d\n", n);

I added one small optimization which didn’t do much and feels unnecessary to skip prime numbers since based on the formula, the solution will never be a prime number.

The entire code is here.

More Advanced Solution?

while the brute force solution is great (good to practice writing all of these methods), you can see above that the formula

$$ \begin{align*} \frac{n}{\phi(n)} &= \frac{p_1 p_2 ... p_k}{ (p_1 - 1) (p_2 - 1) ... (p_k - 1) } \end{align*} $$

is maximized when we have the most distinct prime numbers. So instead we can generate all prime numbers with sieve and then multiply them until we hit the limit \(1,000,000\).


References

Project Euler - 69