Euler Problem 70
================

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 < 10^7, for which φ(n) is a permutation of n and the
ratio n/φ(n) produces a minimum.


```python
from sympy import sieve, primepi
N = 10 ** 7
n = int(N ** 0.5)
min_ratio = 1.005
best_n = None
primes = list(sieve.primerange(1, N))
pi = primepi(n)
num_primes = len(primes)
for i in range(pi, -1, -1):
    p = primes[i]
    ratio = p / (p - 1)
    if ratio > min_ratio:
        break
    for j in range(i+1, num_primes):
        q = primes[j]
        n = p * q
        if n > N:
            break
        if p / (p - 1) > min_ratio:
            break
        if sorted(str(n)) == sorted(str(n - p - q + 1)):
            ratio = 1.0 * p * q / (p - 1) / (q - 1)
            if ratio < min_ratio:
                min_ratio = ratio
                best_n = n
print(best_n)
```

    8319823


**Discussion:** The ratio n/φ(n) is equal to the product of p/(p-1) for all distinct prime factors p of n.
We may assume that n has no repeated factors.

If n is prime then φ(n) = n - 1, so the digits of φ(n) cannot be a permutation of the digits of n.

If n is the product of three or more prime factors, then its smallest prime factor is less than 200, so n/φ(n) > 1.005.

Suppose that n is the product of two distinct prime factors p and q (p < q). Then n/φ(n) = p/(p-1) * q/(q-1). If the minimum value realized in this case is less than 1.005, then we have found the optimal value of n.

cbbfa38232b143692e28897401fa95fe5d4e54c2
ipynb
Jupyter Notebook
Euler 070 - Totient permutation.ipynb
Radcliffe/project-euler
5eb0c56e2bd523f3dc5329adb2fbbaf657e7fa38
MIT
2016-05-11T18:55:35.000Z
2019-12-27T21:38:43.000Z
Euler 070 - Totient permutation.ipynb
Radcliffe/project-euler
5eb0c56e2bd523f3dc5329adb2fbbaf657e7fa38
MIT
Euler 070 - Totient permutation.ipynb
Radcliffe/project-euler
5eb0c56e2bd523f3dc5329adb2fbbaf657e7fa38
MIT
Qwen/Qwen-72B
1. YES
2. YES