# Number of times $2^k$ appears in factorial

For what $n$ does: $2^n | 19!18!...1!$?

I checked how many times $2^1$ appears:

It appears in, $2!, 3!, 4!... 19!$ meaning, $2^{18}$

I checked how many times $2^2 = 4$ appears:

It appears in, $4!, 5!, 6!, ..., 19!$ meaning, $4^{16} = 2^{32}$

I checked how many times $2^3 = 8$ appears:

It appears in, $8!, 9!, ..., 19!$ meaning, $8^{12} = 2^{36}$

I checked how many times $2^{4} = 16$ appears:

It appears in, $16!, 17!, 18!, 19!$ meaning, $16^{4} = 2^{16}$

In all,

$$2^{18} \cdot 2^{32} \cdot 2^{36} \cdot 2^{16} = 2^{102}$$

But that is the wrong answer, its supposed to be $2^{150}$?

• Note that, for example, $6!$ contributes 4 factors of 2 - one from 2, one from 6 and two from 4. You only count 3 of these. – Wojowu Apr 24 '15 at 16:37

A simple trick to compute $k$ such that $2^k|n!$ is to compute $\sum_{i=1}^\infty \left\lfloor\frac{n}{2^i}\right\rfloor$, this is because $n$ has $[n/2]$ numbers divided by $2$, if we pick out these numbers and find out that there're $[n/4]$ numbers divided by $4$.. If we continue this procedure, we see that $$k=1\cdot\left(\left\lfloor\frac{n}{2}\right\rfloor-\left\lfloor\frac{n}{4}\right\rfloor\right)+2\left(\left\lfloor\frac{n}{4}\right\rfloor-\left\lfloor\frac{n}{8}\right\rfloor\right)+\ldots=\sum_{i=1}^\infty \left\lfloor\frac{n}{2^i}\right\rfloor$$. In this case, we have to sum $$0+1+1+3+3+4+4+7+7+8+8+10+10+11+11+15+15+16+16=150.$$ Your fault is that your did not count the contribution of those which is not the power of $2$. For instance, there's $14$ in $14!$..

How many times $2$ divides the product $\prod_{i=1}^{19}i!$ ?

Let's call each term inside a factorial $i$. That way, $i = 1$ occurs in 19 factorials, $i = 2$ occurs in 18 factorials, and $i = 3$ occurs in 17 factorials etc.

$i = 2$ occurs 18 times. $1 \times 18 = 18$
$i = 4$ occurs 16 times. $2 \times 16 = 32$
$i = 6$ occurs 14 times. $1 \times 14 = 14$
$i = 8$ occurs 12 times. $3 \times 12 = 36$
$i = 10$ occurs 10 times. $1 \times 10 = 10$
$i = 12$ occurs 8 times. $2 \times 8 = 16$
$i = 14$ occurs 6 times. $1 \times 6 = 6$
$i = 16$ occurs 4 times. $4 \times 4 = 16$
$i = 18$ occurs 2 times. $1 \times 2 = 2$

$$18 + 32 + 14 + 36 + 10 + 16 + 6 + 16 + 2 = 150$$

It might be more helpful to do this recursively.

Let $T(n) = \prod_{k=1}^n k!$.

We will use the notation: $2^{r} \| m$ to mean that $2^r$ is the largest power of $2$ that divides $m$.

Then we have $2 \| 2! = T(2)$. We also know that $2 \| 3!$, so $2^2 \| T(3) = 3! T(2)$. Continuing:

$$2^3 \| 4!$$ $$2^3 \| 5!$$ $$2^4 \| 6!$$ $$2^4 \| 7!$$ $$2^7 \| 8!$$ $$2^7 \| 9!$$ $$2^8 \| 10!$$ $$2^8 \| 11!$$ $$2^{10} \| 12!$$ $$2^{10} \| 13!$$ $$2^{11} \| 14!$$ $$2^{11} \| 15!$$ $$2^{15} \| 16!$$ $$2^{15} \| 17!$$ $$2^{16} \| 18!$$ $$2^{16} \| 19!$$

If we take the sum of all of those powers, $$2\cdot 1 + 2\cdot 3 + 2\cdot 4 + 2\cdot 7 + 2\cdot8 + 2 \cdot 10 + 2 \cdot 11 + 2 \cdot 15 + 2 \cdot 16$$

$$=2(1+3+4+7+8+10+11+15+16) = 2(75) = 150.$$