## Euler’s totient function, $\phi(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, $\phi(9)=6$.The number $1$ is considered to be relatively prime to every positive number, so $\phi(1)=1$.

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

Find the value of $n$, $1 \lt n \lt 10^7$, for which $\phi(n)$ is a permutation of $n$ and the ratio $n/\phi(n)$ produces a minimum.

### This problem asks us to find an integer n, in the range (1, 1e7), such that the Euler totient function, φ(n), is a permutation of n, and the ratio n / φ(n) is minimized.

This problem is best approached utilizing number theory, and a programming language for the brute-forcing part.

First, we should recognize that φ(n) is maximized when n is a product of distinct primes. This is because φ(n) counts the number of integers less than n that are relatively prime to n – so we want to minimize the number of integers that are not relatively prime to n, or integers that share a factor with n. If n is a product of distinct primes, then fewer integers will share a factor with n.

Secondly, we can notice that for φ(n) and n to be permutations of each other, they likely have to be of the same magnitude. For example, if φ(n) is in the thousands, n is probably in the thousands too, and not in the millions or hundreds.

We can use these two insights to guide our search. We start by generating a list of prime numbers up to some upper limit. Then, for all pairs of primes (we restrict to pairs for computational efficiency), we check whether their product is a permutation of φ(n).

To generate the prime numbers, we can use the Sieve of Eratosthenes, a well-known algorithm for generating all primes up to a given limit. To check whether two numbers are permutations of each other, we can use the built-in sorting functionality.

Doing this, we find that n = 8319823 has the property we want, and produces the minimum value for n / φ(n).

To generalize and create a formal solution for this problem, some form of software programming would be required to efficiently run through all possible values. Checking each candidate manually would be far too time-consuming, so programming really is the only feasible method for solving this problem.

The full Python code capable of solving this problem would be as follows:

“`Python

from sympy import sieve # sympy library is used for extracting prime numbers.

from sympy import totient # totient function

from collections import Counter # Counter function

min_ratio = float(“inf”)

best_n = None

primes = list(sieve.primerange(2000, 5000)) # Get the prime numbers in the given range.

for i in range(len(primes)):

for j in range(i + 1, len(primes)):

n = primes[i] * primes[j]

if n > 1e7:

break

totient_n = (primes[i] – 1) * (primes[j] – 1)

if Counter(str(n)) == Counter(str(totient_n)): # Check if n and φ(n) are permutations.

ratio = n / totient_n

if ratio < min_ratio: # Check if n/φ(n) is a minimum.
min_ratio = ratio
best_n = n
print(best_n)
```
This script will output '8319823' which is the solution to the problem.

##### More Answers:

Maximum Path Sum IIMagic 5-gon Ring

Totient Maximum