Euler’s Totient Function Equals 13!

The first number $n$ for which $\phi(n)=13!$ is $6227180929$.
Find the $150\,000$th such number.

The Euler totient function $\phi(n)$ calculates the number of positive integers that are coprime to (i.e., have no common factor with) the number $n$.

Given the number $n$ such that $\phi(n) = 13!$, it’s not straightforward to find the $150\,000$th such number by employing an analytical solution because there are no direct formulas relating a number and its totient function. Even for relatively simple queries (like finding all numbers with a given totient value), the difficulty is in the fact that the Euler’s totient function follows irregular patterns; even knowing $\phi(n)$ gives limited information about $n$.

A brute-force approach, where you calculate $\phi(n)$ for every integer until you find the 150,000th number such that $\phi(n) = 13!$ would be a computational nightmare due the need to factorize $n$ to find $\phi(n)$, and the sheer number of integers that would need to be tested. For practical reasons, this approach is infeasible.

Therefore, this problem (unless intended for computational purposes) is less about the actual direct computation and more about understanding the nature of Euler’s totient function, its complexities and idiosyncrasies. Formula for the Euler totient function is given by:

$\phi(n) = n*(1 – 1/p_1)*(1 – 1/p_2)*…*(1 – 1/p_k)$

where $p_1, p_2,…, p_k$ are distinct prime numbers dividing $n$.

To compute such value of number $n$, you would need to take into account the prime factorization of that number.

Lastly, the totient function is multiplicative, which means that if $m$ and $n$ are coprime, then $\phi(mn) = \phi(m)\phi(n)$, that can be quite handy in some calculations, but it doesn’t simplify this particular task considerably.

The specific calculation for a 150,000th number with $\phi(n)=13!$ is beyond ordinary manual mathematical calculations. It will need a significant computation power and will involve factoring numbers, trying different possibilities and a number of steps involving the application of number theory, especially the properties of the Euler’s Totient function. That’s why such problems are often solved with programming and algorithms. They are generally outside the realm of pencil and paper mathematics due to the intensity of the computations required.

More Answers: