# Project Euler 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\).

\( 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; }