Problem Solving

If p is the product of the integers from 1 to 30, inclusive, what is the greatest integer k for which 3k is a factor of p?
A. 10 B. 12 C. 14 D. 16 E. 18

OA is C

IMO E

P = 1*2*3*..*30

Let us take the highest integer in choice which is 18

K= 18

We need to check if 3K is a factor of P

P/3K = (1 * 2 * 3 * ... * 30) /( 3 * 18 )
which will be an integer

So E

Please correct me if I am wrong

Something tells me that it should be 3^K instead of 3*k...
Please let me know if that is the case, then I'll explain how the shortcut (Ian's explanations in one of the post from a couple of weeks ago) works with the highest powers possible.

If its 3^K . The answer will be 14.

BTW whats the shortcut?


Thanks
Raama

Hi guys, here is my reasoning:

If in the expression 1*2*3*4*5..*29*30

We find that all the factors integer that are multiple of 3 are

3,6=3*2,9=3*3,12=3*4,15=3*5,18=3*3*2,21=7*3,24=8*3,27=3*3*3,30=10*3

So the maximum is 3^14

In order to calculate the highest power of a prime number in any factorial here is a quick way.....

Let us consider the question itself.....

We have to calculate the highest power of 3 in 30!

The procedure is simple. Go for the successive division.

30/3 = 10

10/3 = 3 (Go for the quotient and don't worry about the remainder)

3/3 = 1

Now add these results i.e. 10+3+1 = 14.

Hence the highest power of 3 in 30! = 14.
---------------------------------------------------------------
---------------------------------------------------------------

Let us look at one more example

Highest power of 7 in 120!

120/7 = 17

17/7 = 2

Hence the highest power of 7 in 120! = 17+2=19

Sometime later I will let you know the logic behind this calculation and also how to calculate highest power of any number in any given product (not only factorial)

Hope this helps

lilu wrote:Something tells me that it should be 3^K instead of 3*k...
Please let me know if that is the case, then I'll explain how the shortcut (Ian's explanations in one of the post from a couple of weeks ago) works with the highest powers possible.

yes it is 3^k