# 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