4
$\begingroup$

I have a number $k$, and I need to find the number of trailing zeros $k!$ (factorial) has when put into base $b$. I need a general way that will work for all $b$'s and $k$'s.

I have tried making variations of the method used for $b=10$, but this has not worked much. The method specifically for $b=10$ is to take the floor of $\dfrac{k}{5^1}$, then to do the take the result and do the same $\left(\dfrac{\frac{k}{5}}{5}\right)$ and keep doing this until the results are under 1. The number of trailing zeros would then be the sum of all these results.

Is there a general way to do something similar for $k!$ in base $b$?

$\endgroup$
1
  • $\begingroup$ Pardon me for my not-so-great style or method of explaining my situation $\endgroup$
    – crownusa
    Dec 13, 2015 at 2:25

1 Answer 1

5
$\begingroup$

Let's suppose our base is $b = p_1^{e_1}p_2^{e_2} \cdots p_k^{e_n}$, where the $p_i$ are prime numbers. The number of trailing zeros of a given number $K$ is the maximum number $m$ such that $b^m = p_1^{e_1m}p_2^{e_2m}\cdots p_n^{e_nm}$ divides $K$.

Let $K = k!$. Then, if we express $k! = q_1^{f_1}q_2^{f_2}\cdots q_r^{f_r}$ as a product of primes $q_i$, we have that the exponent $f_i$ is given by $$f_i = \sum_{s=1}^\infty \left\lfloor\frac{n}{q_i^s} \right\rfloor$$

Now, in order for $b^m$ to divide $k!$, we require that $p_i^{e_i m}$ divides $k!$ for $i = 1,2,\cdots,n$. The number of times that $p_i$ divides $k!$ is, by the previous argument, $$\sum_{s=1}^\infty \left\lfloor\frac{k}{p_i^s} \right\rfloor$$ so, the maximum $m_i$ such that $p_i^{e_im_i}$ divides $k!$ is $$m_i = \left\lfloor \frac{1}{e_i}\sum_{s=1}^\infty \left\lfloor\frac{k}{p_i^s} \right\rfloor\right\rfloor$$ Now, $m \le m_i$ for $i=1,2,\cdots,n$, since if $b^m$ divides $k!$, then certainly the factor $p_i^{e_i}$ does, as well. By the maximality of $m$, we can conclude that $$m = \min_{i=1,2,\cdots, n} m_i = \min_{i=1,2,\cdots, n} \left\lfloor \frac{1}{e_i} \sum_{s=1}^\infty \left\lfloor\frac{n}{p_i^s}\right\rfloor\right\rfloor$$ is the number of trailing zeros when $k!$ is expressed in base $b$.


As an example, let's see how many trailing zeros $16!$ (expressed in the usual base $10$) has in base $b = 12$. We have that $b = 2^2\cdot 3$, so $p_1 = 2$, $p_2 = 3$, and $e_1 = 2$, $e_2 = 1$. Now, we can compute $$m_1 = \left\lfloor \frac{1}{2}\sum_{s=1}^\infty \left\lfloor\frac{16}{2^s}\right\rfloor\right\rfloor = \left\lfloor \frac{8+4+2+1}{2}\right\rfloor = 7$$ $$m_2 = \left\lfloor \frac{1}{1}\sum_{s=1}^\infty \left\lfloor\frac{16}{3^s}\right\rfloor\right\rfloor = 5 + 1 = 6$$ so $16!$ (again, in decimal) has $$m = \min\{7,6\} = 6$$ trailing zeros when expressed in base $12$. We can check this in WolframAlpha, which tells us that $$(16!)_{10} = 241ab88000000_{12}$$ indeed has $6$ trailing zeros.

$\endgroup$
2
  • $\begingroup$ What happens if $k=b$? $\endgroup$ Dec 20, 2015 at 21:30
  • $\begingroup$ @Sky The equations still function identically if $k=b$. For example, let's see how many trailing zeros $12!$ has in base $12$. We have: $$m_1 = \left\lfloor \frac{1}{2}\sum_{s=1}^\infty \left\lfloor\frac{12}{2^s}\right\rfloor\right\rfloor = \left\lfloor \frac{6+3+1}{2}\right\rfloor = 5$$ $$m_2 = \left\lfloor \frac{1}{1}\sum_{s=1}^\infty \left\lfloor\frac{16}{2^s}\right\rfloor\right\rfloor = 4 + 1 = 5$$ so $12!$ has $5$ trailing zeros when expressed in base $12$. Indeed, WolframAlpha says $12! = 114500000_{12}$. $\endgroup$
    – user88319
    Dec 20, 2015 at 23:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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