bunuel

How did we decide to use 5 in point no . 1, I mean what is the complete question to the example

Is it no. of trailing zero's when 32! is divided by 5 , In the second case its apparent that we are dividing by the prime factors .

But in order to find the no. of trailing zero's of n! what should we divide by ?

Can someone please explain this part of the above topic??? thanks
"The formula actually counts the number of factors 5 in , but since there are at least as many factors 2, this is equivalent to the number of factors 10, each of which gives one more trailing zero."

If I go to excel and calculate factorial 50! and then divide by 900^6, i still have room for 900^7 which then still yields a positive result. Could you explain that further?

3.04141E+64 =50!
5.31441E+17 =900^6
5.722948210942210000000000E+46 =Quotient (50!/900^6)

Thank you very much

FACTORIALS

This post is a part of [GMAT MATH BOOK]

created by: Bunuel
edited by: bb, Bunuel

--------------------------------------------------------

Definition

The factorial of a non-negative integer \(n\), denoted by \(n!\), is the product of all positive integers less than or equal to \(n\).

For example: \(4!=1*2*3*4=24\).

Properties

• Factorial of a negative number is undefined.
• \(0!=1\), zero factorial is defined to equal 1.
• \(n!=(n-1)!*n\), valid for \(n\geq{1}\).

Trailing zeros:

Trailing zeros are a sequence of 0's in the decimal representation of a number, after which no other digits follow. For example: 125,000 has 3 trailing zeros;

The number of trailing zeros in the decimal representation of n!, the factorial of a non-negative integer \(n\), can be determined with this formula:

\(\frac{n}{5}+\frac{n}{5^2}+\frac{n}{5^3}+...+\frac{n}{5^k}\), where \(k\) must be chosen such that \(5^k\leq{n}\)

Example:
How many zeros are in the end (after which no other digits follow) of 32!?

\(\frac{32}{5}+\frac{32}{5^2}=6+1=7\). Notice that the denominators must be less than or equal to 32 also notice that we take into account only the quotient of division (that is \(\frac{32}{5}=6\) not 6.4). Therefore, 32! has 7 trailing zeros.

The formula actually counts the number of factors 5 in \(n!\), but since there are at least as many factors 2, this is equivalent to the number of factors 10, each of which gives one more trailing zero.

Finding the powers of a prime number p, in the n!

The formula is:
\(\frac{n}{p}+\frac{n}{p^2}+\frac{n}{p^3}+...+\frac{n}{p^k}\), where \(k\) must be chosen such that \(p^k\leq{n}\)

Example:
What is the power of 2 in 25!?

\(\frac{25}{2}+\frac{25}{4}+\frac{25}{8}+\frac{25}{16}=12+6+3+1=22\).

_________________________________________________________________________________________________
Questions to practice:
http://gmatclub.com/forum/if-60-is-writ ... 01752.html
http://gmatclub.com/forum/how-many-zero ... 00599.html
http://gmatclub.com/forum/find-the-numb ... 08249.html
http://gmatclub.com/forum/find-the-numb ... 08248.html
http://gmatclub.com/forum/if-n-is-the-p ... 01187.html
http://gmatclub.com/forum/if-m-is-the-p ... 08971.html
http://gmatclub.com/forum/if-p-is-a-nat ... 08251.html
http://gmatclub.com/forum/if-10-2-5-2-i ... 06060.html
http://gmatclub.com/forum/p-and-q-are-i ... 09038.html
http://gmatclub.com/forum/question-abou ... 08086.html
http://gmatclub.com/forum/if-n-is-the-p ... 06289.html
http://gmatclub.com/forum/what-is-the-g ... 05746.html
http://gmatclub.com/forum/if-d-is-a-pos ... 26692.html
http://gmatclub.com/forum/if-10-2-5-2-i ... 06060.html
http://gmatclub.com/forum/how-many-zero ... 42479.html

Bunuel
Could you please explain what >> The formula actually counts the number of factors 5 in n!n!, but since there are at least as many factors 2, this is equivalent to the number of factors 10, each of which gives one more trailing zero
means from above? Thank you!

Hi,

I just went through this thread. I understand point# 1 about trailing zeroes. However, for the life of me, I cant understand Point#2.
Can anyone please explain me what are we really trying to solve in "2. Finding the number of powers of a prime number k, in the n!."

For the question "What is the power of 2 in 25!", the answer is given as 22. What does it mean ?

Thanks

Bunuel chetan2u KarishmaB niks18 GMATPrepNow EMPOWERgmatRichC

What is the rationale behind choosing 5 and its powers in the denominator?
for e.g. in terminating decimals I need to know whether the denominator contains either of 2 or 5 or its powers, else the long division may go indefinitely.

If I do not recall this formula in exam under timed condition, is there any alternate approach to this?

Say, a and b are two integers.

a/b = a * 1/b

For a/b to be terminating, 1/b must be a terminating decimal. What happens when you start dividing 1 by b? You add a decimal point and start adding 0s.You will get 1 followed by as many 0s as you require in the numerator. 10/100/1000/10000 etc have only two prime divisors: 2 and 5. If the denominator has 2s or 5s or both, we will be able to terminate the decimal by choosing the required multiple of 10. If there are any other primes, we will never be able to divide a multiple of 10 completely and hence the decimal will not terminate. It is obvious, isn’t it?

Thank you KarishmaB for your two cents.

Below is a relevant quote from your blog:



Why do we not need to need to know whether b is greater than (or not) 1? I could not understand highlighed text in context of long division, Can you elaborate?

I would be grateful if you could explore an additional approach for factorial problem. TIA.

Yes, it is. I've separated them as for GMAT generally we need only trailing zeros and almost never other prime's power.



It's better to illustrate it on the example:
How many powers of 900 are in 50!
\(900=2^2*3^2*5^2\)


Find the power of 2:
\(\frac{50}{2}+\frac{50}{4}+\frac{50}{8}+\frac{50}{16}+\frac{50}{32}=25+12+6+3+1=47\)

= \(2^{47}\)


Find the power of 3:
\(\frac{50}{3}+\frac{50}{9}+\frac{50}{27}=16+5+1=22\)

=\(3^{22}\)


Find the power of 5:
\(\frac{50}{5}+\frac{50}{25}=10+2=12\)

=\(5^{12}\)

We need all of them (2,3,5) to be represented twice in 900, 5 can provide us with only 6 pairs, thus there is 900 in the power of 6 in 50!
900^6

Bunuel

Valuable post! +1



Can you please post this one too? It's still interesting, though may not be usable for GMAT

You won't need this for GMAT but still let's see if we can do it:

First we should make prime factorization of 20!. 20! will have all primes from 0 to 20, so we should find the powers of these primes in 20!.

Powers of 2 --> \(\frac{20}{2}+\frac{20}{4}+\frac{20}{8}+\frac{20}{16}=10+5+2+1=18\);
Powers of 3 --> \(\frac{20}{3}+\frac{20}{9}=6+2=8\);
Powers of 5 --> \(\frac{20}{5}=4\);
Powers of 7 --> \(\frac{20}{7}=2\);
Powers of 11 --> \(\frac{20}{11}=1\);
Powers of 13 --> \(\frac{20}{13}=1\);
Powers of 17 --> \(\frac{20}{17}=1\);
Powers of 19 --> \(\frac{20}{19}=1\).

So \(20!=2^{18}*3^8*5^4*7^2*11^1*13^1*17^1*19^1\).

Next: How to Find the Number of Factors of an Integer.

First make prime factorization of an integer \(n=a^p*b^q*c^r\), where \(a\), \(b\), and \(c\) are prime factors of \(n\) and \(p\), \(q\), and \(r\) are their powers.

The number of factors of \(n\) will be expressed by the formula \((p+1)(q+1)(r+1)\). NOTE: this will include 1 and n itself.

Example: Finding the number of all factors of 450: \(450=2^1*3^2*5^2\)

Total number of factors of 450 including 1 and 450 itself is \((1+1)*(2+1)*(2+1)=2*3*3=18\) factors.


So, the # of positive factors of \(20!=2^{18}*3^8*5^4*7^2*11^1*13^1*17^1*19^1\) will be \((18+1)(8+1)(4+1)(2+1)(1+1)(1+1)(1+1)(1+1)=19*9*5*3*2*2*2*2=41040\).

The same way we can find for 720!, but we'll need much more time.

Hope it helps.