Project Euler Solution #69: Totient maximum

Euler's Totient function, \( \varphi (n)\) [sometimes called the phi function], is used to determine the number of numbers less than 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, \( \varphi (9)=6\).

It can be seen that n=6 produces a maximum  \( \frac{n}{\varphi (n)}\) for n ≤ 10.

Find the value of n ≤ 1,000,000 for which  \( \frac{n}{\varphi (n)}\) is a maximum.

Solution

The Totient function can be defined with Euler's product formula with the product of a numbers distinct prime numbers:

\[{\displaystyle \varphi (n)=n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right)}\]

It can be seen that the more distinct primes a number has, the smaller the totient function will become. Since we want to minimize \(\varphi (n)\) and maximize \(n\) to maximize

\[\frac{n}{\varphi (n)} = \frac{n}{n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right)} =\frac{1}{\prod _{p\mid n}\left(1-{\frac {1}{p}}\right)} = \prod\limits _{p\mid n}{\frac {p}{p-1}}, \]

all we have to do is creating a number \(n\) by building the product of all primes until we reach the limit.

This can be solved pretty straightforward with pen and paper: \(n=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\leq 10^6\). For a general limit, this simple snippet can be implemented:

function solution(L) {
  var n = 1, k = 0;
  var primes = [2, 3, 5, 7, 11, 13, 17, 19, 21, 23, 29, 31];
  while (primes[k] * n <= L)
    n*= primes[k++];
  return n;
}