greatest integer

[[email protected]]

If n is the product of the integers from 1 to 20 inclusive, what is the greatest integer k for which 2^k is a factor of n ?
A) 10
B)12
C)15
D)18
E)20

D

[amitabhprasad]

There should be some smarter way.
but I took all the even numbers between 1 and 20
and summed up the multiples of 2
for example
2*4*6*8*10
can be written as = 2*(2^2)*(2*3)*(2^3)*(2*5)
# of multiple of 2's = 1+2+1+3+1 = 8
similarly you can do the same for
12,14,16,18 and 20
12 = 2^2*3
14 = 2*7
16 = 2^4
18 = 2*9
20 = 2^2*5
# of 2's = 10
And you get the total as 18

[Sachindh]

If n is the product of the integers from 1 to 20 inclusive, what is the greatest integer k for which 2^k is a factor of n ?
A) 10
B)12
C)15
D)18
E)20

D

Since we are looking for 2^k as a factor for k should have greatest value then n should be multiplication of even numbers between 2 to 20.
Thus
2 * 4* 6*8*10*12*14*..20
=> 2 ^(1+2+1+3+1+2+1+4+1+2)
=> 2^(18)

Hence 18 should be answer.
Is their any super smart way to solve this question?

[vittalgmat]

I did the same way of listing all the even nums and writing them as powers of 2 to get the answer 18. Since this takes less than 2, I will use it on problems of this type.

However, if somebody has a smarter soln, I would love to know.

There is one related takeaway
Product of n consecutive numbers is divisible by n!

eg 200*201*202 is divisible by 3!

[ronniecoleman]

Posted: Mon Dec 29, 2008 6:43 pm Post subject: greatest integer
If n is the product of the integers from 1 to 20 inclusive, what is the greatest integer k for which 2^k is a factor of n ?
A) 10
B)12
C)15
D)18
E)20


product= 1*2*3......20

there are 10 even numbers

2^10( 1*3*2*5*6....*10)

Still 5 even no,

2^10 * 2^5 ( 1*3* 1*5..)


keeping on
we get 2^18

[manulath]

Product from 1 to 20

[b]20/2[/b] = 10 ---------for all numbers divisible by 2^1

[b]20/4[/b] = 5 -----------for all numbers divisible by 2^2

[b]20/8[/b] = 2.5 ---------for all numbers divisible by 2^3

[b]20/16 [/b]= 1.25-------for all numbers divisible by 2^4

[b]20/32 [/b]= 0.625------for all numbers divisible by 2^5

[b]Add all whole numbers leaving away the decimal part
10 + 5 + 2 + 1 + 0 = 18[/b]

this is done in detail. theres actually no need to calculate the decimals.
32 was just doen to show as an exmple. Moment the denominator becomes larger than numerator, it will be always less than 1.

Since the number was small it was easy to list out the numbers.
Suppose, it was from 1 to 100 or 1 to 1000!

[cramya]

I remember explaining the shortcut in a different post. Ian also had provided a conceptual explanation of why this shortcut works . Let me try to find it if possible. Its a good shortcut to know.


Like Manulath has mentioned keep dividing 20 by increasing powers of 2 starting with 2^1 and add all the quotients in the process i.e till u get a quotient of 1 (ignoring 20/2^5 since the quotient is 0)


Works for any factorial. If the problem was 30! then u would do the same thing with one change

30/2^1 + 30/2^2 ........


Lets say we have to find the highest power of 10 in 20 factorial then 10=2*5

We have to do 20/5^1 + 20/5^2
= 4 + 0
= 4

Think about this 10^4 beacuse 5 contributes one 5, 10 contributes one 5, 15 contributes one 5 and 20 contributes the last 5. Even though there are more 2's, 5's limit the powers of 10.

The reason why we take 5 and not 2 this time is because the limiting power would be 5 since there are more 2's than 5's in 20 factorial.


Hope this helps!

[sogmat]

If n is the product of the integers from 1 to 20 inclusive, what is the greatest integer k for which 2^k is a factor of n ?
A) 10
B)12
C)15
D)18
E)20



k this is my approach

20/2=10
10/2=5
5/2=2
2/2=1

and then just add 10+5+2+1=18

[vineetbatra]

Friends,

I tried to apply similar logic for another question where 20 is replaced by 30. I get 2^26, i.e.
30/2 = 15
15/2 = 7
7/2 = 3
3/2 =1
Total = 26

however when I try to solve this in excel i.e. divide 30! by 2^27 or 2^28 or until 2^61 the remainder is zero.

I seem to be missing the point here, can someone please explain the logic behind this solution I want to be able to apply this logic in other quesions also.

Thanks,

Vineey

[tohellandback]

we need to find how many 2's are there in 20!

it is 20/2 + 20/4 +20/8 +20/16
=10+5+2+1
=18
answer D

[vineetbatra]

we need to find how many 2's are there in 20!

it is 20/2 + 20/4 +20/8 +20/16
=10+5+2+1
=18
answer D

I am trying to use this logic with 30 instead of 20, to see if this is a universally acceptable logic.

[tohellandback]

we need to find how many 2's are there in 20!

it is 20/2 + 20/4 +20/8 +20/16
=10+5+2+1
=18
answer D

I am trying to use this logic with 30 instead of 20, to see if this is a universally acceptable logic.

it will work with 30.
but if you need to make it work with 40
you need to add the additional term, 40/32
the point is you all to count the terms which contain more that 1 2's
4 contains 2
8 contains 3
and so on

[vineetbatra]

it will work with 30.
but if you need to make it work with 40
you need to add the additional term, 40/32
the point is you all to count the terms which contain more that 1 2's
4 contains 2
8 contains 3
and so on

can you please show me the break up of 30, when I tried to do it for 30 I got 26 and their are exponents of 2 greater than 26 that are factors of 30!

[tohellandback]

it will work with 30.
but if you need to make it work with 40
you need to add the additional term, 40/32
the point is you all to count the terms which contain more that 1 2's
4 contains 2
8 contains 3
and so on

can you please show me the break up of 30, when I tried to do it for 30 I got 26 and their are exponents of 2 greater than 26 that are factors of 30!

for 30, it is
30/2 + 30/4 +30/8 +30/16
=15+7+3+1
=26
there is no way there can be more than 26 2's
let me count:
2-1
4-2
6-1
8-3
10-1
12-2
14-1
16-4
18-1
20-2
22-1
24-3
26-1
28-2
30-1
Add all of them- there are 26

[vineetbatra]

for 30, it is
30/2 + 30/4 +30/8 +30/16
=15+7+3+1
=26

I totally agree that it is 26 and I apologise if I am unable to explain my probelm, however my point is 2^27 is also a factor of 30! i.e. when 30! is divided by 2^27 then the remainder is zero, try it in excel.