Énoncé:
La fonction indicatrice d'Euler, $\varphi(n)$ (parfois appelé la fonction phi), est utilisée pour determiner le nombre d'entiers inférieurs à $n$ et qui lui sont relativement premier. Par exemple, comme $1, 2, 4, 5, 7$ et $8$ sont tous inférieurs à $9$ et lui sont tous relativement premier, alors $\varphi(9) = 6$.
| n | Nombres relativement premiers | $\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\dots$ |
| $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$ |
On peut voir que $n = 6$ produit un maximum pour $n / \varphi(n)$ pour $n \le 10$.
Trouve la valeur de $n \le 1 \ 000 \ 000$ pour laquelle $n / \varphi(n)$ est maximisé.
Lien du problème originel