The following theorem reveals a remarkable formula for the factorial using prime numbers and the floor function.

Theorem: Number of Multiples of a Prime Number Less Than Factorial

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 ( * * )$$

Example

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


Thank you to the contributors under CC BY-SA 4.0!

Github:
bookofproofs


References

Bibliography

  1. Landau, Edmund: "Vorlesungen ├╝ber Zahlentheorie, Aus der Elementaren Zahlentheorie", S. Hirzel, Leipzig, 1927