1
$\begingroup$

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}$?

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Wojowu Apr 24 '15 at 16:37
2
$\begingroup$

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!$..

$\endgroup$
0
$\begingroup$

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$$

$\endgroup$
0
$\begingroup$

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.$$

$\endgroup$

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.