Factorial

The factorial is an important function in combinatorics and analysis, used to determine the number of ways to arrange objects.

Since $n!$ is the product of all positive integers not exceeding $n$ , it is clear that it is divisible by all primes $p\le n$ , and not divisible by any prime $p>n$ . But what is the power of a prime $p\le n$ in the prime factorization of $n!$ ? We can find it as the sum of powers of $p$ in all the factors $1,2,\dots, n$ ; but rather than counting the power of $p$ in each factor, we shall count the number of factors divisible by a given power of $p$ . Among the numbers $1,2,\dots,n$ , exactly $\left\lfloor\frac n{p^k}\right\rfloor$ are divisible by $p^k$ (here $\lfloor\cdot\rfloor$ is the floor function). The ones divisible by $p$ give one power of $p$ . The ones divisible by $p^2$ give another power of $p$ . Those divisible by $p^3$ give yet another power of $p$ . Continuing in this manner gives

$\left\lfloor\frac n{p}\right\rfloor+ \left\lfloor\frac n{p^2}\right\rfloor+ \left\lfloor\frac n{p^3}\right\rfloor+\dots$

for the power of $p$ in the prime factorization of $n!$ . The series is formally infinite, but the terms converge to $0$ rapidly, as it is the reciprocal of an exponential function. For example, the power of $7$ in $100!$ is just $\left\lfloor\frac {100}{7}\right\rfloor+ \left\lfloor\frac {100}{49}\right\rfloor=14+2=16$ ( $7^3=343$ is already greater than $100$ ).