The following theorem reveals a remarkable formula for the factorial using prime numbers and the floor function.
Let p\in\mathbb P be a prime number, n > 0 be a natural number and n!=n\cdot (n-1)\cdot (n-2)\cdot\ldots\cdot 2\cdot 1 its factorial. The number k of multiples of p, i.e. the numbers p,2p,3p,\ldots,kp with kp\le n! is given by the sum using the floor function:
k=\sum_{m=1}^\infty\left\lfloor\frac n{p^m}\right\rfloor.\quad \quad ( * )
In particular, the factorial n! can be written as a product of powers of all primes:
n!=\prod_{p\in\mathbb P}p^{\sum_{m=1}^\infty\left\lfloor\frac n{p^m}\right\rfloor}.\quad \quad ( * * )
For n=1000, and p=3 we have
\begin{array}{c}\left\lfloor\frac {1000}{3}\right\rfloor=333,\quad\left\lfloor\frac {1000}{3^2}\right\rfloor=111,\quad \left\lfloor\frac {1000}{3^3}\right\rfloor=37,\\ \left\lfloor\frac {1000}{3^4}\right\rfloor=12,\quad\left\lfloor\frac {1000}{3^5}\right\rfloor=4,\quad\left\lfloor\frac {1000}{3^6}\right\rfloor=1\end{array} and the sum is 333+111+37+12+4+1=498. Thus, in the factorization of huge factorial number 1000! the power 3^{498} occurs. We would have got the same result at a significantly lower cost if we had applied a property of floors (the 7th there) that \left\lfloor\frac {x}{n}\right\rfloor=\left\lfloor\frac {\lfloor x\rfloor}{n}\right\rfloor. Because \left\lfloor\frac {n}{p^{m+1}}\right\rfloor=\left\lfloor\frac {\left\lfloor \frac{n}{p^m}\right\rfloor}{p}\right\rfloor,
we can calculate much simpler like this:
\begin{array}{c}\left\lfloor\frac {1000}{3}\right\rfloor=333,\quad\left\lfloor\frac {333}{3}\right\rfloor=111,\quad \left\lfloor\frac {111}{3}\right\rfloor=37,\\ \left\lfloor\frac {37}{3}\right\rfloor=12,\quad\left\lfloor\frac {1000}{3}\right\rfloor=4,\quad\left\lfloor\frac {1000}{3}\right\rfloor=1.\end{array}
Proofs: 1
