What is longer? Length of $2^n$ or number of $0$ in $n!$?

Question

What is longer? Length of $2^n$ or number of $0$ at the end of $n!$ ? Assume that $n$ is really big, big number...

Solution

Look at terms of $2^k$: $$2,4,8,16,32,64,128,256,512,1024,2048,4096... $$ It can be seen that $$ \lfloor\frac{n}{3} \rfloor \ge length(2^n)\ge \lfloor\frac{n}{4} \rfloor $$

Now, lets look at $n!$. We know that $0$ is created at the end iif we use $2$ and $5$ or $10$. Number of $2$ is greater than number of $5$ so we can count number of $5$.

$$\mbox{number of 0 in } n! = \sum_{k \ge 0} \lfloor\frac{n}{10^k} \rfloor + \sum_{k \ge 0} \lfloor \frac{n}{5^k} \rfloor $$

$$ (n-1)\left( \sum_{k \ge 0} \frac{1}{10^k} + \sum_{k \ge 0} \frac{1}{5^k} \right)\ge \mbox{number of 0 in } n! \ge n \left( \sum_{k \ge 0} \frac{1}{10^k} + \sum_{k \ge 0} \frac{1}{5^k} \right) $$ $$ \mbox{number of 0 in } n! \approx \frac{13}{36} \cdot n \approx 0.361 \cdot n \ge \frac{1}{3} \cdot n $$

So the longer is number of $0$ in $n!$. Have I done this exercise correctly?

update

$$ (n-1)\left( \sum_{k \ge 0} \frac{1}{5^k} \right)\ge \mbox{number of 0 in } n! \ge n \left( \sum_{k \ge 0} \frac{1}{5^k} \right) $$ $$ \mbox{number of 0 in } n! \le 1/4 $$ so length of 2^n is greater that trailing $0$ in $n!$

Answer 1

Denote by $l(n)$ the number of digits of $2^n$ and by $t(n)$ the number of trailing zeros of $n!$. We aim to show that $t(n) < l(n)$, at least for large $n$.

Per the update, the number of trailing zeros in $n!$ is the number of factors of $5$ in the prime factorization of $n!$, and it follows from the definition of factorial that this is $$t(n) = \sum_{k \geq 0} \left\lfloor\frac{n}{5^k}\right\rfloor .$$

The definition of $\lfloor \,\cdot\, \rfloor$ implies that $\lfloor m \rfloor \leq m$, so (as nearly observed in the question statement) $$t(n) \leq \sum_{k \geq 0} \frac{n}{5^k} = n \sum_{k \geq 0} \frac{1}{5^k} = \frac{1}{4} n .$$

To make rigorous the rest of the argument, we should formalize the assertion "It can be seen that..." as an inequality and then use it to show that $t(n) < l(n)$.

Hint To do this, we can use a familiar formula $$l(n) = \lfloor \log_{10} (2^n) \rfloor + 1 = \lfloor n \log_{10} 2 \rfloor + 1 .$$ The definition of $\lfloor \,\cdot\, \rfloor$ implies that $m \leq \lfloor m \rfloor + 1$, immediately giving the lower bound $$(\log_{10} 2) n \leq l(n) .$$

Comparing our bounds, we can see that if we can show $$\phantom{(\ast)} \qquad \frac{1}{4} < \log_{10} 2 , \qquad (\ast)$$ then we will have $$t(n) \leq \frac{1}{4} n < (\log_{10} 2) n \leq l(n)$$ as desired (in fact, for all $n > 0$, not just large $n$). But some algebraic rearrangement shows that $(\ast)$ is equivalent to $10 < 16$.