Project Euler Problem 70 Solution

Question

Euler’s Totient function, φ(n)\varphi(n) [sometimes called the phi function], is used to determine the number of positive numbers less than or equal to nn which are relatively prime to nn. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6\varphi(9)=6. The number 1 is considered to be relatively prime to every positive number, so φ(1)=1\varphi(1)=1.

Interestingly, φ(87109)=79180\varphi(87109)=79180, and it can be seen that 87109 is a permutation of 79180.

Find the value of nn, 1<n<1071 \lt n \lt 10^7, for which φ(n)\varphi(n) is a permutation of nn and the ratio nφ(n)\frac{n}{\varphi(n)} produces a minimum.

Haskell

Python

Ruby