Project Euler 69 Solution: Totient maximum

Problem 69

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\).

\( n\) Relatively Prime \( \varphi (n)\) \( n/\varphi (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  \( \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;
}

« Back to problem overview