Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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: $(100/2)+(100/4)+(100/8)+(100/16)+(100/32)+(100/64)=97$

Number of trailing zeros$=97/4=24$.

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

share|improve this question
1  
For some basic information about writing math at this site see e.g. here, here, here and here. –  Julian Kuelshammer Nov 1 '12 at 16:57
    
I'm pretty sure this is a dupe of an earlier question on using de Polignac-Legendre... –  J. M. Nov 1 '12 at 17:12

3 Answers 3

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.

share|improve this answer

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*}

share|improve this answer

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.

share|improve this answer
    
Where can I get a proof to Equation (1) ? :) –  Manoj Pandey Sep 12 at 15:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.