Owl Test Prep

Factors in Factorials 1

posted on

For how many positive integer values of n is 5^n a factor of 50! ?

(A) 11      (B) 12      (C) 13      (D) 14      (E) 15

Translation

Obviously, 5^1 and 5^2 are factors of 50! . We need to know the largest  n such that 5^n is a factor of 50! . It should be clear that we can’t just start dividing 50! by larger and larger powers of 5 until we get a non-zero remainder. Factorials get REALLY big REALLY fast! For example,

10! = 3,629,800

50! has more than 60 digits!

Good Enough

This problem isn’t going down to a frontal assault, so we need to find a back door. Another way to think about the question would be “how many fives are in the prime factorization 50 factorial?” Listing the prime factors of the integers between 1 and 50 and checking for numbers with factors of 5 is impractical, but multiples of 5 are easy to pick out, and since there are only 10 multiples of 5 between 1 and 50 listing the multiples of 5 isn’t impractical at all.

Multiples  Number of 5s  Total 
5 1 1
10 1 2
15 1 3
20 1 4
25 2 6
30 1 7
35 1 8
40 1 9
45 1 10
50 2 12

You have to watch out for factors of 25, but other than that it’s relatively simple and efficient – maybe not 2-minute efficient, but time management is about management, not a set limit for each problem.

800

The ten multiples of 5 between 1 and 50 get us 10 factors of 5. However there are other fives hidden in multiples of 25. There are two multiples of 25 between 1 and 50 so we have to count two more fives. Because we are only going up to 50!, this isn’t much quicker than the first method. But if we had a larger factorial, we could start counting 125’s, then 625’s, and so on, allowing us to count much more efficiently than we could with a table or list.

Using this solution on this problem is a bit like using an RPG to kill a large mosquito However, this method is the way to go when confronted with some larger flying pest/predator… maybe a pterodactyl? Anyway, what if the test writers asked you to find the number of positive integer values of n such that 5^n is a factor of 1000! ? I’ll let you try this one yourself. Watch out for hidden fives! Hopefully, you’ll find 249 5’s.

The correct answer is (B)