Euler’s Totient function, φ(n) [sometimes called the phi
function], is used to determine the number of positive numbers
less than or equal to 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, φ(9)=6. The number 1 is considered to
be relatively prime to every positive number, so φ(1)=1.
Interestingly, φ(87109)=79180, and it can be seen that 87109 is
a permutation of 79180. Find the value of n, 1 <n < 107, for
which φ(n) is a permutation of n and the ratio n/φ(n) produces a
minimum. We can reduce our search significantly by selecting
prime pairs (p1, p2 ) and calculate n as n = p1 x p2. This
allows the totient to be calculated as The range of primes was
selected by taking the square root of the upper bound,
10,000,000, which is about 3162 and taking ±30% for a range of
primes from 2000 to 4000 (247 primes). Runs < 1 second in
Python. from Euler import prime_sieve, is_perm, sqrt L = 10**7
primes = prime_sieve(int(1.30*sqrt(L))) del prime