7
$\begingroup$

I know that this may be an unnecessary question, but I am a bit confused. The problem asks for the highest integer $n$ such that $8$ to the power of $n$ is divisible, evenly of course, by $100$. Now, I searched the site, and, in general, it seems that one can use floor function for a problem like this, but this seems to only work for prime numbers possibly. My process, which I realized was incorrect:

The floor function of $100/8 = 12$, and then doing it for the second power would lead to one, and, by adding those up, I acquired thirteen. Of course, after seeing the answer, $32$, I went back to see what was wrong and did the problem slower. I got $12$ numbers from the numbers in $100!$, and then got another $8$ from $2 \times 4$, but, that can be applied for all the multiples of $2$ and $4$ that aren't of $8$. So, essentially, I am wondering if there is a quicker method for calculating this number without specifically counting out the numbers. Thanks in advance!

$\endgroup$
  • 1
    $\begingroup$ are you talking about (100!) or (100) ? $\endgroup$ – Seth Feb 13 at 22:59
  • $\begingroup$ I intended for it to be meant as (100!) with a question mark at the end. $\endgroup$ – Unknown Feb 13 at 23:00
  • $\begingroup$ Edited title for easier reading. Thanks for the concern. $\endgroup$ – Unknown Feb 13 at 23:01
  • $\begingroup$ Is it $8^n$ is divisible by $100$ or $8^n$ divides $100!\,$? $\endgroup$ – Bernard Feb 13 at 23:07
  • $\begingroup$ It is the second one ( 8^n divides (100!) ) $\endgroup$ – Unknown Feb 13 at 23:09
9
$\begingroup$

I think the easiest way to answer this question is to factorize $100!$. Actually, a partial factorization will be sufficient. Thus, we see that $$100! = 2^{97} \times 3^{48} \times 5^{24} \times \ldots \times 83 \times 89 \times 97.$$

Since $8 = 2^3$, we need to divide $97$ by $3$ and discard the remainder. That is, rewrite $2^{96}$ as $8^n$ and there's your answer.

$\endgroup$
  • $\begingroup$ Thanks for the answer! I was hoping that there was a quicker method (maybe an algorithmic one). $\endgroup$ – Unknown Feb 13 at 23:14
  • $\begingroup$ Thanks for the suggestion (I'm new to the site, so, I don't know how to make this work). $\endgroup$ – Unknown Feb 13 at 23:15
  • 1
    $\begingroup$ This suggests to me the following algorithm: repeatedly divide the factorial by 2, increment a counter as you do so, until you get an odd number, specifically a number from oeis.org/A049606 $\endgroup$ – Robert Soupe Feb 14 at 2:44
9
$\begingroup$

It's easiest, I think, to do this with powers of $2:$

$$\left\lfloor{100\over2}\right\rfloor+ \left\lfloor{100\over4}\right\rfloor+ \left\lfloor{100\over8}\right\rfloor+ \left\lfloor{100\over16}\right\rfloor+ \left\lfloor{100\over32}\right\rfloor+ \left\lfloor{100\over64}\right\rfloor=97=32\cdot3+1 $$

so the greatest exponent of $8$ is $32$.

$\endgroup$
  • $\begingroup$ Thanks for the answer! $\endgroup$ – Unknown Feb 13 at 23:13
  • 1
    $\begingroup$ This is known as Legendre's formula. $\endgroup$ – Bernard Feb 13 at 23:35
  • 1
    $\begingroup$ @Bernard Reading mathworld.wolfram.com/LegendresFormula.html I'm not quite sure this is right, though it's definitely related. Of course it's also possible I have misunderstood. $\endgroup$ – Mr. Brooks Feb 14 at 23:58
8
$\begingroup$

Just sum up the $2$-adic orders of the even numbers from $2$ to $100$

You get that $$(100)! = 2^{97}\cdot A=8^{32}\cdot 2A$$ where $A$ is the product of all the remaining (odd) factors of $100!$

$\endgroup$
  • $\begingroup$ Thanks for taking the time to answer! $\endgroup$ – Unknown Feb 13 at 23:20
  • $\begingroup$ You're welcome. Hope it helps. $\endgroup$ – Rhys Hughes Feb 13 at 23:21
5
$\begingroup$

So you're looking for roughly a third of $$n = \sum_{i = 1}^\infty \left\lfloor \frac{m}{p^i} \right\rfloor,$$ where $m = 100$ and $p$ is 2 ($m$ can be any positive integer and $p$ can be any odd prime).

Of course you don't actually have to even try to go to infinity. As soon as you notice $$\frac{m}{p^i} < 1,$$ you can stop the iteration.

The important thing to understand here is that each consecutive number by which you multiply to get a factorial "adds" its prime factors' exponents to the factorial's prime factors' exponents.

For example, $11! = 2^8 \times 3^4 \times 5^2 \times 7 \times 11 \times 13^0 \times 17^0 \times 19^0 \times \ldots$ Since $12 = 2^2 \times 3^{(1)}$, we can just add 2 to 2's exponent and 1 to 3's exponent, to obtain $12! = 2^{10} \times 3^5 \times 5^2 \times 7 \times 11 \times 13^0 \times$ $17^0 \times 19^0 \times \ldots$ And then the factorization of 13! is a simple matter of adding 1 to 13's exponent.

So in the specific case you're looking at, the first question is: how many numbers less than or equal to 100 are even? Half of them, giving you 50. But this doesn't account for how many of them are "doubly even," since they contribute at least 2 each to 2's exponent in the factorization of 100! So there's 25 of those, bringing our tally up to 75.

And then twelve of them are divisible by 8 (tally's 87 now), six are divisible by 16 (tally 93), three are divisible by 32 (tally 96), only one one is divisible by 64 (tally 97), and none are divisible by 128, 256, 512, 1024, etc. (tally stays at 97).

All that's left to do now is to solve $2^{97} = 8^x$, and round down $x$ if necessary.

$\endgroup$
1
$\begingroup$

Well $8^n = 2^{3n}$ so it will do to find the highest power of $2$ which divide $100!$.

Which means considering the prime factorization of $100!= 2^k*3^j*5^m.....$. What is $k$ in the $2^k$?

Well $100! = 1 * 2 * 3* 4* ....... *97*98*99*100$ but only the even numbers contribute to powers of $2$.

So $100! = 2*4*6*......*98*100*($ a bunch of odd terms$)=$

$= (2*1)*(2*2)*(2*3)*..... *(2*49)*(2*50)*($ the odd terms $)=$

$= 2^{50}*(1*2*3*4*.....*50)*($ the odd terms $)$.

Now the even terms of $1,2,3,4,...., 50$ are going to contribute to powers of $2$ so

$100! = 2^{50}*(2*4*6*...*48*50)*($ the odd terms up to fifty$)*($ a heck of a lot of odd terms$)=$

$2^{50}*(2*1)*(2*2)*(2*3)*.....*(2*24)*(2*25)*($ just a huge honkin amount of odd terms that we hae utterly no need to keep track of$)=$

$2^{50}*2^{25}*(1*2*3.....*25)*($ sh!tload of odd terms$)=$

$2^{50}*2^{25}*(2*4*....*24)*($ something odd $)=$

$2^{50}*2^{25}*2^{12}*(1*2*3*....*12)*($ odd monster $)=$

$2^{50}*2^{25}*2^{12}*(2*4*6*8*10*12)*($ odd thing $)=$

$2^{50}*2^{25}*2^{12}*2^6*(1*2*3*4*5*6)*$ ODD$)=$

$2^{50}*2^{25}*2^{12}*2^6*(2*4*6)*$ MEGA-ODD$)=$

$2^{50}*2^{25}*2^{12}*2^6*2^3*(1*2*3)*$ ODDasaurus $)=$

$2^{50}*2^{25}*2^{12}*2^6*2^3*2^1*$ MEGA-MECHA-ODD-atron-a-galactadingy.

So $100! = 2^{50+25+12+6+3+1}*M$ where $M$ is an odd number.

$100! = 2^{97}*M= 2^{3*32}*2*M= 8^{32}*2*M$.

So $8^{32}|100!$ but $8^{33}$ does not.

====

In general.

To find the highest power of prime $p$ that divides $N!$ realize that of the terms $1..... N$ that $[\frac Np]$ of those terms are mulitples of $p$ so $p^{[\frac Np]}$ will divide $N!$.

However $[\frac N{p^2}]$ of those terms are not just multiples of $p$ but of $p^2$ and these term contribute $[\frac N{p^2}]$ additional powers of $p$.

Repeating until we are done:

The highest power of $p$ dividing $100!$ will be $p^{[\frac Np] + [\frac N{p^2}] + [\frac N{p^3}] + ......}$.

In the case of $2$ and $100!$ it was

$2^{[\frac {100}2] + [\frac {100}4 ]+ [\frac {100}8] + [\frac {100}{16}[ + [\frac {100}{32}] + [\frac {100}{64}]}=2^{50 + 25 + 12+ 6 + 3+ 1}$.

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