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.
Think of this problem as a high-stakes search. We are looking for a number where the "Euler Totient" (let's call it the Partner Number) is a permutation of the original number (like 123 and 321), and the ratio between them is as small as possible.
1. The "Partner Number" \(\phi\)
In math, every number has a "Totient" \(\phi\). This is simply a count of how many numbers smaller than it don't share any common factors with it.
- For a Prime (e.g., 7): Every number below it is a "friend" \((1, 2, 3, 4, 5, 6)\). So \(\phi(7) = 6\).
- For a Composite (e.g., 10): Only \(1, 3, 7\), and \(9\) are "friends." So \(\phi(10) = 4\).
The problem asks for the smallest ratio of \(\frac{n}{\phi(n)}\). Mathematically, this ratio is smallest when the number is mostly made of large prime factors.
2. The Linear Sieve (The Fast Factory)
Imagine you have to find the Partner Number for every single integer up to 10,000,000. If you did this one by one, it would take hours.
The Linear Sieve is like a factory assembly line. Instead of calculating from scratch, it uses a simple rule: if you know the Partner Number for \(10\), you can instantly figure it out for \(20, 30\), or \(70\). By "building" the numbers using their prime factors, the program visits every number exactly once. This is what makes it fast enough to pass the time limit.
3. The "Bouncer" (The Ratio Guard)
Checking if two numbers are permutations (like \(1234\) and \(4321\)) is actually quite slow for a computer because it has to turn the numbers into strings and sort their digits.
To save time, we use a Ratio Guard. Before checking for a permutation, we ask: "Is the current ratio even better than the best one we've found so far?"
- If No: We ignore the number and move on instantly.
- If Yes: Only then do we do the hard work of checking the digits.
Because the "winning" ratio is very small, this "Bouncer" lets us skip the hard work for 99.9% of all numbers.
4. The Permutation Check
When a number finally passes the "Bouncer," we check if it’s a permutation. We do this by:
- Converting the number to a string (e.g.,
"1210"). - Sorting the characters (e.g.,
["0", "1", "1", "2"]). - Comparing it to the sorted version of its Partner Number. If they match, we have a new champion!
HackerRank version
HackerRank Project Euler Problem 70: Find the value of $n, 1\lt n\lt N$, for which $\phi(n)$ is a permutation of $n$ and the ratio $n/\phi(n)$ produces a minimum. $100\le N\le 10^7$
Python Source Code
def solve(L):
phi, primes, best_n, min_ratio = list(range(L)), [], 0, 2.0
is_p = [0] * L
for i in range(2, L):
if not is_p[i]:
primes.append(i); phi[i] = i - 1
for p in primes:
if i * p >= L: break
is_p[i * p] = 1
if i % p == 0:
phi[i * p] = phi[i] * p; break
phi[i * p] = phi[i] * (p - 1)
if i / phi[i] < min_ratio:
if sorted(str(i)) == sorted(str(phi[i])):
min_ratio, best_n = i / phi[i], i
return best_n
print(solve(int(input())))