Prime Powers in n!

$100!$ has 158 digits. How many of them are zeros at the end? You do not need to compute it. By unique factorization, the question is how many factors of $2$ and $5$ are hiding in $1 \cdot 2 \cdot 3 \cdots 100$, and there is a formula for that.

Legendre's formula. For a prime $p$, the exponent of $p$ in $n!$ is $$\left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^{2}} \right\rfloor + \left\lfloor \frac{n}{p^{3}} \right\rfloor + \cdots,$$ where $\lfloor x \rfloor$ is the floor, the largest integer at most $x$. The sum stops once $p^{k} > n$.

Por qué funciona

Every number $m$ from $1$ to $n$ contributes its own exponent of $p$ to $n!$. Count those contributions by layers. Every multiple of $p$ contributes at least one factor: there are $\lfloor n/p \rfloor$ of them. Every multiple of $p^{2}$ contributes a second one: $\lfloor n/p^{2} \rfloor$ more. Every multiple of $p^{3}$ a third, and so on. A number like $m = 50 = 2 \cdot 5^{2}$ is counted once in the first layer and once in the second, exactly its two factors of $5$.

Ejemplo resuelto: One prime

Find the exponent of $2$ in $20!$.

$\lfloor 20/2 \rfloor = 10$ multiples of $2$.
$\lfloor 20/4 \rfloor = 5$ multiples of $4$, $\lfloor 20/8 \rfloor = 2$ of $8$, $\lfloor 20/16 \rfloor = 1$ of $16$.
Total: $10 + 5 + 2 + 1 = 18$. So $2^{18}$ divides $20!$, and $2^{19}$ does not.

Respuesta: $18$.

Ejemplo resuelto: Zeros at the end

How many zeros does $100!$ end with?

Each final zero is a factor $10 = 2 \cdot 5$. There are far more $2$s than $5$s, so count the $5$s.
$\lfloor 100/5 \rfloor + \lfloor 100/25 \rfloor = 20 + 4 = 24$ (and $125 > 100$).

Respuesta: $24$ zeros.

Ejemplo resuelto: A composite base

What is the largest $k$ with $12^{k} \mid 30!$?

$12 = 2^{2} \cdot 3$, so each copy of $12$ needs two $2$s and one $3$.
$2$s in $30!$: $15 + 7 + 3 + 1 = 26$, enough for $13$ copies. $3$s: $10 + 3 + 1 = 14$, enough for $14$ copies.
The $2$s run out first: $k = 13$.

Respuesta: $k = 13$.

Error común

Counting only the multiples of $5$. "$100/5 = 20$ zeros" misses that $25$, $50$, $75$ and $100$ each bring a second factor of $5$. Keep adding $\lfloor n/p^{k} \rfloor$ until the terms reach $0$. A quick sanity check: $25! = 15{,}511{,}210{,}043{,}330{,}985{,}984{,}000{,}000$ ends in $6$ zeros, and $5 + 1 = 6$.

There are more $2$s than $5$s in $n!$ because every second number is even but only every fifth is a multiple of $5$. A neat second form of the formula uses base $p$: the exponent of $p$ in $n!$ is $\dfrac{n - s}{p - 1}$, where $s$ is the sum of the digits of $n$ in base $p$. For $100 = 400_5$: $(100 - 4)/4 = 24$.

Idea clave

The exponent of $p$ in $n!$ is $\sum_{k \ge 1} \lfloor n/p^{k} \rfloor$. For trailing zeros, count the $5$s.

Práctica

Se apoya en

Lleva a

Fuentes y lecturas