What is the number of trailing zeros in a factorial in base ‘b’?

I know the formula to calculate this, but I don't understand the reasoning behind it:

For example, the number of trailing zeros in $100!$ in base $16$:

$16=2^4$,

We have: $\frac{100}{2}+\frac{100}{4}+\frac{100}{8}+\frac{100}{16}+\frac{100}{32}+\frac{100}{64}=97$

Number of trailing zeros$ =\frac{97}{4} = 24$.

Why do we divide by the power of '$2$' at the end?

Solution 1:

Suppose that $b=p^m$, where $p$ is prime; then $z_b(n)$, the number of trailing zeroes of $n!$ in base $b$, is

$$z_b(n)=\left\lfloor\frac1m\sum_{k\ge 1}\left\lfloor\frac{n}{p^k}\right\rfloor\right\rfloor\;.\tag{1}$$

That may look like an infinite summation, but once $p^k>n$, $\left\lfloor\frac{n}{p^k}\right\rfloor=0$, so there are really only finitely many non-zero terms.

The summation counts the number of factors of $p$ in $n!$. The set $\{1,2,\dots,n\}$ of integers whose product is $n!$ contains $\left\lfloor\frac{n}p\right\rfloor$ multiples of $p$, $\left\lfloor\frac{n}{p^2}\right\rfloor$ multiples of $p^2$, and so on $-$ in general $\left\lfloor\frac{n}{p^k}\right\rfloor$ multiples of $p^k$. Each multiple of $p$ contributes one factor of $p$ to the product $n!$; each multiple of $p^2$ contributes an additional factor of $p$ beyond the one that was already counted for it as a multiple of $p$; each multiple of $p^3$ contributes an additional factor of $p$ beyond the ones already counted for it as a multiple of $p$ and as a multiple of $p^2$; and so on.

Let $s=\sum_{k\ge 1}\left\lfloor\frac{n}{p^k}\right\rfloor$; then $n!=p^sk$, where $k$ is not divisible by $p$. Divide $s$ by $m$ to get a quotient $q$ and a remainder $r$: $s=mq+r$, where $0\le r<m$. Then $$n!=p^sk=p^{mq+r}k=(p^m)^qp^rk=b^qp^rk\;,$$ where $p^rk$ is not divisible by $b$. Since $p^rk$ isn’t divisible by $b$, in base $b$, it will not end in $0$. Multiplying it by $b$ will simply tack a $0$ on the righthand end of it, just as multiplying $123$ by $10$ in base ten tacks a $0$ on the end to make $1230$. Multiplying by $b^q$ is multiplying by $b$ a total of $q$ times, so it tacks $q$ zeroes onto a number that did not end in $0$; the result is that $n!$ ends up with $q$ zeroes in base $b$. But $$q=\left\lfloor\frac{s}m\right\rfloor=\left\lfloor\frac1m\sum_{k\ge 1}\left\lfloor\frac{n}{p^k}\right\rfloor\right\rfloor\;,$$ showing that $(1)$ is correct.

In your example $b=2^4$, so $p=2$ and $m=4$, and with $n=100$, $(1)$ becomes

$$\begin{align*} z_{16}(100)&=\left\lfloor\frac14\sum_{k\ge 1}\left\lfloor\frac{100}{2^k}\right\rfloor\right\rfloor\\\\ &=\left\lfloor\frac14\left(\left\lfloor\frac{100}2\right\rfloor+\left\lfloor\frac{100}4\right\rfloor+\left\lfloor\frac{100}8\right\rfloor+\left\lfloor\frac{100}{16}\right\rfloor+\left\lfloor\frac{100}{32}\right\rfloor+\left\lfloor\frac{100}{64}\right\rfloor\right)\right\rfloor\\\\ &=\left\lfloor\frac14(50+25+12+6+3+1)\right\rfloor\\\\ &=\left\lfloor\frac{97}4\right\rfloor\\\\ &=24 \end{align*}$$

The value of the summation is $97$, which tells you that there are $97$ factors of $2$ in $100!$: $100!=2^{97}k$, where $k$ is an odd number. $97=4\cdot24+1$, so $100!=2^{4\cdot24+1}k=(2^4)^{24}2k=16^{24}(2k)$, where $2k$ is not a multiple of $16$ (since it’s just $2$ times an odd number). Thus, the base $16$ representation of $2k$ does not end in $0$. Each of the $24$ multiplications of this number by $16$ tacks another $0$ on the end in base $16$, so you end up with $24$ zeroes on the end.

The original sum counts the factors of $2$ in $100!$, but the number of zeroes on the end isn’t the number of factors of $2$: it’s the number of factors of $2^4$, the base. Every four factors of $2$ give you one factor of $2^4$, so you divide by $4$ (and throw away the remainder) to see how many factors of $2^4$ you can build out of your $97$ factors of $2$.

When the base is not a power of a prime, counting the trailing zeroes is a little harder, but it can be done using exactly the same ideas.

Solution 2:

The count of $97$ is the count of powers of $2$ in the factorial. In base $16$, every group of powers of $2$ leads to one zero digit: $2^4=10_{16}$ has one zero, $2^8=100_{16}$ has two zeros, and so on.

By the way, you need floor signs around those divisions; the convention that the result of dividing two integers is rounded down to an integer is applied in programming languages but not in mathematics.

Solution 3:

Let $p$ be a prime (in your example, you'd have $p = 2$). We aim to find the largest $k\in \mathbb N$ with $p^k \mid n!$, so we have to count the factors $p$ in $1, \ldots, n$. If $k_1$ is the number of these which are a multiple of $p$, we have that $k_1p \le n$ and $k_1$ is largest with this property, so $k_1 = \lfloor \frac np\rfloor$. But this is not all, as we can have multiples of $p^2$ below $n$ which give another factor of $p$ each (one factor has been counted), there are $\lfloor \frac n{p^2}\rfloor$ of them. Going on like this, we find \[ k_p = \sum_{i = 1}^\infty\left\lfloor \frac n{p^i}\right\rfloor \] factors $p$ in $n!$.

The number of trailing zeros in the base $q$ representation of $n!$ is the maximal number $k$ such that $q^k \mid n!$, writing $q$ as a product of prime powers $q = \prod_p p^{\alpha_p}$, we have that $q^k \mid n!$ iff $p^{k\alpha_p} \mid n!$ for each $p$. So we must have $k \alpha_p \le k_p$ for each $p$, and the maximal $k$ for which this holds is \[ k = \min \left\{\left\lfloor \frac{k_p}{\alpha_p}\right\rfloor\biggm| p \mid q \text{ prime} \right\} \] In the case $q = 2^4$, we have thus $\alpha_2 = 4$ and hence (as you calculated) \begin{align*} k_2 &= 97\\ \alpha_2 &= 4\\ k &= 24. \end{align*}