BREAKING: Target Test Prep releases Brand New 2026 On Demand GMAT prep course

Redeem

greatest integer

This topic has expert replies
Post new topic Post Reply
Previous Topic Next Topic
Source: — Problem Solving |
Master | Next Rank: 500 Posts
Posts: 259
Joined: Thu Jan 18, 2007 8:30 pm
Thanked: 16 times

by amitabhprasad » Mon Dec 29, 2008 7:16 pm
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
Top
Senior | Next Rank: 100 Posts
Posts: 37
Joined: Wed Sep 17, 2008 8:17 pm
Location: India
Thanked: 4 times

Re: greatest integer

by Sachindh » Mon Dec 29, 2008 7:39 pm
[email protected] wrote: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?
Top
Legendary Member
Posts: 621
Joined: Wed Apr 09, 2008 7:13 pm
Thanked: 33 times
Followed by:4 members

by vittalgmat » Mon Dec 29, 2008 10:59 pm
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!
Top
User avatar
Legendary Member
Posts: 546
Joined: Sun Nov 16, 2008 11:00 pm
Location: New Delhi , India
Thanked: 13 times

by ronniecoleman » Mon Dec 29, 2008 11:13 pm
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
Admission champion, Hauz khaz
011-27565856
Top
Senior | Next Rank: 100 Posts
Posts: 35
Joined: Tue Sep 09, 2008 10:12 pm
Location: Lko
Thanked: 3 times

by manulath » Tue Dec 30, 2008 5:12 am
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!
Top
Legendary Member
Posts: 2467
Joined: Thu Aug 28, 2008 6:14 pm
Thanked: 331 times
Followed by:11 members

by cramya » Tue Dec 30, 2008 6:33 am
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!
Top
Master | Next Rank: 500 Posts
Posts: 113
Joined: Tue Oct 21, 2008 9:43 pm
Location: Mumbai
Thanked: 1 times

by sogmat » Tue Dec 30, 2008 8:08 pm
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
Top
User avatar
Master | Next Rank: 500 Posts
Posts: 355
Joined: Thu Feb 19, 2009 12:42 pm
Thanked: 2 times
Followed by:1 members

by vineetbatra » Mon Aug 17, 2009 1:40 pm
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
Top
Legendary Member
Posts: 752
Joined: Sun May 17, 2009 11:04 pm
Location: Tokyo
Thanked: 81 times
GMAT Score:680

by tohellandback » Mon Aug 17, 2009 7:55 pm
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
The powers of two are bloody impolite!!
Top
User avatar
Master | Next Rank: 500 Posts
Posts: 355
Joined: Thu Feb 19, 2009 12:42 pm
Thanked: 2 times
Followed by:1 members

by vineetbatra » Mon Aug 17, 2009 8:07 pm
tohellandback wrote: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.
Top
Legendary Member
Posts: 752
Joined: Sun May 17, 2009 11:04 pm
Location: Tokyo
Thanked: 81 times
GMAT Score:680

by tohellandback » Mon Aug 17, 2009 8:12 pm
vineetbatra wrote:
tohellandback wrote: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
The powers of two are bloody impolite!!
Top
User avatar
Master | Next Rank: 500 Posts
Posts: 355
Joined: Thu Feb 19, 2009 12:42 pm
Thanked: 2 times
Followed by:1 members

by vineetbatra » Mon Aug 17, 2009 8:15 pm
tohellandback wrote: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!
Top
Legendary Member
Posts: 752
Joined: Sun May 17, 2009 11:04 pm
Location: Tokyo
Thanked: 81 times
GMAT Score:680

by tohellandback » Mon Aug 17, 2009 8:23 pm
vineetbatra wrote:
tohellandback wrote: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
The powers of two are bloody impolite!!
Top
User avatar
Master | Next Rank: 500 Posts
Posts: 355
Joined: Thu Feb 19, 2009 12:42 pm
Thanked: 2 times
Followed by:1 members

by vineetbatra » Mon Aug 17, 2009 8:28 pm
tohellandback wrote: 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.
Top
Post new topic Post Reply
• Page 1 of 1