Official Guide Problem #110

[GHong14]

This question comes from the Official Guide 12th Edition:

Problem 110 in Quant. Problem Solving:

If p is the product of the integers from 1 to 30, inclusive, what is the greatest integer k for which 3 ^k is a factor of P?

A) 10
B) 12
C) 14
D) 16
E) 18

This OG solves this problem by listing a table of numbers between 3 and 30 and finding all the possible factors of 3 for each of the numbers. I am wondering if there is an easier way to solve this problem. There has to.....

Any Suggestions!?!??!!?

[Rahul@gurome]

p is 30!.
Now divide 30 by 3. You get 10 integers between 1 and 30 which are divisible by 3.
Again divide 30 by 9. You get 3 3/9. This means 3 integers between 1 and 30 are divisible by 9.
Next divide 30 by 27. You get 1 3/27. This means 1 integer between 1 and 30 is divisible by 27.
So the power of 3 in 30! Is 10+3+1 = 14.
So k = 14.
The correct answer is C).

[GHong14]

Thank you so much!

Care you briefly explain why dividing 30 but powers of 3 works in this problem?

[Rahul@gurome]

Thank you so much!

Care you briefly explain why dividing 30 but powers of 3 works in this problem?

When we divide 30/3 we get 10 integers which are multiples of 3.
So 10 of them give us 10 powers of 3, but the multiples of 9 will give us 1 extra power because 9 = 3^2.
Since 30/9 = 3 3/9, 3 multiples of 3 will give us 1 extra power each. Or we get 3 more powers of 3.
Similarly multiples of 27 will again give us 1 extra power each because 27 = 3^3. Note that we do not take 2 extra powers because 1 has already been taken when we are considering multiples of 9. This is because any multiple of 27 is also a multiple of 9.
And we have 30/27 = 1 3/27. Or 1 multiple of 3 will give us 1 extra power.
Hence k = 10+3+1 = 14.