0
$\begingroup$

This question already has an answer here:

If $90! = (90)(89)(88)...(2)(1)$, then what is the exponent of the highest power of $2$ which will divide $90!$ ?

How would I apply one of the easiest method from Here?

I need help on applying the link to this question.

I do not understand which one explains my case, and how I can solve using the method.

I would appreciate if someone showed how it is applied to this

$\endgroup$

marked as duplicate by lab bhattacharjee, JimmyK4542, Kamil Jarosz, user91500, didgocks Feb 2 '16 at 16:08

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ @labbhattacharjee I apologize if this is a duplicate, but I do not quite understand the link that you have provided. $\endgroup$ – didgocks Feb 2 '16 at 15:36
  • 1
    $\begingroup$ That is a post that deals with the general case of how many times a prime (in your case $p=2$ is the prime) will divide a factorial (in your case 90!). Do you not see how it applies, or do you not see how the computation there is carried out, or do you not see why it is true? Please narrow down what part you "do not quite understand" and Readers will be glad to help. $\endgroup$ – hardmath Feb 2 '16 at 15:42
  • $\begingroup$ @hardmath I might need help with applying the method in the link to my problem $\endgroup$ – didgocks Feb 2 '16 at 15:46
  • $\begingroup$ Your idea was a good first step: there are $45$ even factors between $1$ and $90$, which gives us at least that many factors of $2$ in the product (factorial). But this leaves out counting powers of two which arise from multiples of $4$, of $8$, etc. The given answers show how to put all of them together. $\endgroup$ – hardmath Feb 2 '16 at 17:39
6
$\begingroup$

We know that there are $\lfloor \frac{90}{2}\rfloor$ integers below $90$ that have at least one factor $2$, $\lfloor \frac{90}{4}\rfloor$ numbers that have $2$ factors $2$, etc. Thus, the number of factors $2$ in $90!$ is $$\sum_{k=1}^{\infty}\left\lfloor \frac{90}{2^k}\right\rfloor=86$$ We don't actually have to do this sum up to $\infty$, but only until $6$, since there's no numbers under $90$ with more than $6$ factors. However, this form is more easily generalizable, which is always nice.

$\endgroup$
0
$\begingroup$

Hint:

Your intuition isn't that bad. There are indeed $45$ even factors, hence $2^{45}$. But some factors still have other powers of $2$ (like $4=2^2$ or $48=2^4\cdot3$).

Look at what happens if you erase the odd factors and divide all the even ones by $2$...

You obtain the recurrence $$p(n)=\lfloor \frac n2\rfloor+p\left(\lfloor \frac n2\rfloor\right).$$

$\endgroup$

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