Ceros al Final de los Factoriales

Teoría

El número de ceros al final en la representación entera de un factorial $n!$ corresponde al exponente de la mayor potencia de 10 que divide a $n!$. Como $10 = 2 \times 5$, obtienes un cero al final por cada pareja de factores primos 2 y 5 en la factorización prima de $n!$. Algo fundamental en este tema es notar que, en la secuencia de los números naturales, los múltiplos de 2 aparecen mucho más seguido que los múltiplos de 5. Por lo tanto, la potencia de 2 que divide a $n!$ siempre es mayor o igual a la potencia de 5 que divide a $n!$.

Así que el número de parejas $(2, 5)$ está limitado estrictamente por la cantidad de factores 5. Para encontrar el número de ceros al final, basta con calcular el exponente del primo 5 en la factorización prima de $n!$, que escribes como $v_5(n!)$. Esto reduce el problema de analizar bases compuestas a calcular la valuación $p$-ádica de un factorial, lo cual resuelves de forma elegante con la Fórmula de Legendre.

Aunque este concepto lo evalúas casi siempre en base 10, la lógica se extiende a cualquier base $b$. Si quieres encontrar el número de ceros al final de $n!$ en base $b$, analiza la factorización prima de $b$. Si $b = p_1^{e_1} \cdots p_k^{e_k}$, el número de ceros lo determina el factor primo $p_i$ que sea el "reactivo limitante" respecto a su exponente necesario $e_i$. En la notación decimal estándar, esto simplemente confirma que tienes que contar los factores de 5.

Fórmulas Clave

1. Ceros al final en base 10 El número de ceros al final de $n!$, denotado como $Z(n)$, lo obtienes aplicando la Fórmula de Legendre con $p=5$: $$ Z(n) = v_5(n!) = \sum_{k=1}^{\infty} \left\lfloor \frac{n}{5^k} \right\rfloor = \left\lfloor \frac{n}{5} \right\rfloor + \left\lfloor \frac{n}{25} \right\rfloor + \left\lfloor \frac{n}{125} \right\rfloor + \cdots $$ Nota que la suma es finita porque los términos se vuelven 0 en cuanto $5^k > n$.

2. Fórmula de Legendre (General) El exponente de un primo $p$ en la factorización prima de $n!$ es: $$ v_p(n!) = \sum_{k=1}^{\infty} \left\lfloor \frac{n}{p^k} \right\rfloor $$

3. Fórmula de Legendre (Forma de suma de dígitos) Una formulación alternativa que es útil para demostraciones teóricas y ciertas restricciones computacionales involucra a $s_p(n)$, la suma de los dígitos de $n$ cuando lo escribes en base $p$: $$ v_p(n!) = \frac{n - s_p(n)}{p - 1} $$

4. Ceros al final en una base general $b$ Sea la factorización prima de la base $b = p_1^{e_1} p_2^{e_2} \cdots p_m^{e_m}$. El número de ceros al final de $n!$ en base $b$ es: $$ Z_b(n) = \min_{1 \le i \le m} \left\lfloor \frac{v_{p_i}(n!)}{e_i} \right\rfloor $$

Demostración

Teorema: El exponente de la mayor potencia de un primo $p$ que divide a $n!$ está dado por $v_p(n!) = \sum_{k=1}^{\infty} \lfloor \frac{n}{p^k} \rfloor$.

Demostración: Lo que buscas es contar el número total de factores de $p$ en el producto $n! = 1 \times 2 \times 3 \times \cdots \times n$.

Considera la contribución de cada entero $m \in {1, \dots, n}$ al total. El entero $m$ aporta $v_p(m)$ a la suma total. Por lo tanto, lo que quieres calcular es: $$ v_p(n!) = \sum_{m=1}^{n} v_p(m) $$ En lugar de sumar la valuación de cada número individualmente, vas a contar "capa por capa":

1. Primero, cuenta qué números en el producto aportan al menos un factor de $p$. Estos son los múltiplos de $p$: $p, 2p, 3p, \dots$. La cantidad de estos múltiplos menores o iguales a $n$ es $\lfloor \frac{n}{p} \rfloor$.
2. Luego, cuenta qué números aportan un segundo factor de $p$. Estos son los múltiplos de $p^2$: $p^2, 2p^2, 3p^2, \dots$. La cantidad de estos múltiplos es $\lfloor \frac{n}{p^2} \rfloor$. Nota que estos números ya los contaste una vez en el paso 1; aquí estás tomando en cuenta su segundo factor de $p$.
3. En general, para cualquier entero $k \ge 1$, la cantidad de enteros en ${1, \dots, n}$ que son múltiplos de $p^k$ es $\lfloor \frac{n}{p^k} \rfloor$. Este paso cuenta el $k$-ésimo factor de $p$ que aportan estos números.

Sumar estos conteos cubre cada factor de $p$ exactamente una vez por cada vez que aparece en la factorización de un número del conjunto. Por ejemplo, un número con exactamente $j$ factores de $p$ (es decir, un múltiplo de $p^j$ pero no de $p^{j+1}$) lo contarás exactamente $j$ veces: una vez en el conteo de $p$, otra para $p^2$, ..., y una última para $p^j$.

Así, el exponente total es la suma sobre todas las potencias $k$: $$ v_p(n!) = \sum_{k=1}^{\infty} \left\lfloor \frac{n}{p^k} \right\rfloor $$ Para el caso específico de los ceros al final en base 10, toma $p=5$, lo que te da la fórmula que viste en la sección anterior. $\square$