Функция Эйлера, φ(n) [иногда ее называют фи-функцией] используется для определения количества чисел, меньших n, которые взаимно просты с n. К примеру, т.к. 1, 2, 4, 5, 7 и 8 меньше девяти и взаимно просты с девятью, φ(9) = 6.
Число 1 считается взаимно простым для любого положительного числа, так что φ(1) = 1.

Интересно, что φ(87109) = 79180, и, как можно заметить, 87109 является перестановкой 79180.

Найдите такое значение n, 1 < n < 10⁷, при котором φ(n) является перестановкой n, а отношение n/φ(n) является минимальным.