Tuesday, August 2, 2011

How many zeros does 1000! end with?

Is it easy to find the number of zeros 1000! ends with? The answer is YES, it is very straight forward and the answer is 249.
[For the people who does not understand n!(n Factorial).
     1000! is called '1000 factorial' which is equivalent to 1 x 2 x 3 ...x1000.

The answer is [1000/5] + [1000/5^2 ] + [1000/5^3 ] + [1000/5^4 ]...  
             = [1000/5] + [1000/25] +[1000/125] + [1000/625]
             = 200 + 40 + 8 +1 = 249
( [n/p] stands for integer part of n/p. For instance [3/2 ] is 1 and [5/6] is 0. in computer terms FLOOR)

Rest of this post is only for the people who wants to know little more about the mathematical theorem stands behind this solution

Theorem:
if N is an integer, P is a prime number and N! = p^s . m then s = [ n/p]v+ [n/p^3] + [n/p^4]...


in our case N = 1000 and s is the solution we are looking for.What is the value for P? 10? but the theorem says P must be a prime number and 10 is not prime. But you know what 10 = 2 X 5 also 2 and 5 are prime numbers.
So instead of finding exponents of 10 in 1000!, we can find exponent values of 2 and 5 in 1000! and minimum value will be exponent value of 10 in 1000!
 In other words, if we can find the exponent value of 5 in 1000! we can happily say that many number of zeros will be at the end of 1000!.

No comments: