Prime Factorisation of Binomial Coefficients

The binomial coefficient $\displaystyle \binom {10} 3 = 120$.
$120 = 2^3 \times 3 \times 5 = 2 \times 2 \times 2 \times 3 \times 5$, and $2 + 2 + 2 + 3 + 5 = 14$.
So the sum of the terms in the prime factorisation of $\displaystyle \binom {10} 3$ is $14$.

Find the sum of the terms in the prime factorisation of $\displaystyle \binom {20\,000\,000} {15\,000\,000}$.

To solve this problem, we must understand the concept of Legendre’s formula, which provides the highest power of a prime number that divides N!.

Legendre’s Formula states:
\[v_p (n!) = \sum_{k=1}^{\infty} \lfloor \frac{n}{p^k} \rfloor \]

In this formula, \(\lfloor x \rfloor\) is the greatest integer less than or equal to \(x\), and \(v_p (n!)\) is the highest power of the prime \(p\) that divides \(n!\).

Now, we know that \(\binom{n}{k} = \frac{n!}{k!(n-k)!}\). Therefore, if we need to find the power of a prime \(p\) in \(\binom{n}{k}\), we can use Legendre’s formula as follows:

\[v_p \binom{n}{k} = v_p (n!) – v_p (k!) – v_p ((n-k)!)\]

Once we have the power of each prime \(p\) in the prime factorization of \(\binom{n}{k}\), we can then simply multiply each prime’s power by the prime number itself to find the sum of the prime’s terms in the prime factorization of \(\binom{n}{k}\).

Unfortunately, due to the large size of the numbers 20,000,000 and 15,000,000, calculating the sum of terms in the prime factorization of \(\binom{20\,000\,000}{15\,000\,000}\) directly through factorizing will run into computational issues and could possibly even exceed the capability of most calculators or software.

For such large numbers, you may need a script or program that can effectively iterate and perform these calculations. Additionally, computing prime factorizations of very large numbers falls into the realm of advanced computational mathematics and computer science, specifically the area related to number-theoretic methods and cryptographic applications.

**To summarize:** Theoretically to find the sum of the terms in prime factorisation of \(\binom{20000000}{15000000}\), one would use Legendre’s formula to first find the power of each prime in the prime factorization and then compute the sum by multiplying each prime’s power by the prime itself. However, due to the large size of the numbers, this computation is not feasible on a small scale and such challenges generally require advanced computational techniques or programming.

More Answers: