Project Euler Problem 70 Statement
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.
Solution
HackerRank's Project Euler 70 asks us to find a number $n$ where $\phi(n)/n$ is minimized and $\phi(n)$ is a permutation of $n$. Here, $\phi(n)i$ is Euler's totient function, which counts how many numbers less than n are coprime to n. For example, $\phi(9) = 6$ because six numbers (1,2,4,5,7,8) are coprime to 9.
The solution uses Euler's product formula to efficiently calculate totient values. Instead of checking each number for coprimality (which would be very slow), we use the fact that for a prime number $p$, $\phi(p) = p-1$, and for prime powers, $\phi(p^k) = p^k - p^{k-1}$. For composite numbers, the totient function is multiplicative, meaning we can break it down into its prime factors. This is why we use a sieve-like approach in the code.
The is_permutation() function simply converts numbers to strings and compares their sorted digits. For example, 123 and 321 are permutations because they have the same sorted digits [1,2,3]. This helps us identify when $\phi(n)$ is a permutation of $n$.
The main loop in solve() builds up totient values using the sieve method. When we find a prime number (identified by phi[i] == i), we update all its multiples according to Euler's formula. For each number, we calculate the ratio $n/\phi(n)$ and check if it's both smaller than our current minimum and forms a permutation.
HackerRank version
HackerRank Project Euler 70: Find the value of $n$, $1\lt n\lt N (100\le N\le 10^7)$, for which is a permutation of $n$ and the ratio $n/\phi(n)$ produces a minimum.
Python Source Code
def is_permutation(a, b):
return sorted(str(a)) == sorted(str(b))
def solve(limit):
phi = list(range(limit))
min_ratio = float('inf')
result = 0
# Calculate all totients using sieve method
for i in range(2, limit):
if phi[i] == i: # i is prime
for j in range(i, limit, i):
phi[j] = phi[j] * (i - 1) // i
# Check if current number is a solution
if i > 1:
ratio = i / phi[i]
if ratio < min_ratio and is_permutation(i, phi[i]):
min_ratio = ratio
result = i
return result
print(solve(int(input())))