Tough prime factorisation problem

Expert replies

selango: Legendary Member; Posts: 1460; Joined: Tue Dec 29, 2009 1:28 amFollowed by: 7 members; Thanked: 135 times

by selango » Mon Jul 05, 2010 6:38 am

For any integer k > 1, the term "length of an integer" refers to the number of positive prime factors, not necessarily distinct, whose product is equal to k. For example, if k = 24, the length of k is equal to 4, since 24 = 2 Ã— 2 Ã— 2 Ã— 3. If x and y are positive integers such that x > 1, y > 1, and x + 3y < 1000, what is the maximum possible sum of the length of x and the length of y?

A.5
B.6
C.15
D.16
E.18

OA D

can anyone explain in detail?

--Anand--

Like this post

Source: Beat The GMAT — Problem Solving | Mon Jul 05, 2010 6:38 am

kvcpk: Legendary Member; Posts: 1893; Joined: Sun May 30, 2010 11:48 pmFollowed by: 7 members; Thanked: 215 times

by kvcpk » Mon Jul 05, 2010 7:00 am

Hi Anand,

The wording of the problem is very difficult.

I will expalin How I approached the problem. Others can suggest even better ways.

Given x + 3y < 1000
Now the number of prime factors need to be maximum for both x and y.

Logically, the maximum number of prime multiples that can be accommodated is when the number has more 2 multiples.

So, I took x to be some power of 2.

Let us say 2^10 ->1024 INSUFFICIENT.
2^9 = 512 -> We still need to find y
now 512 + 3(2^p) <1000
3(2^p)<488
2^p<162

So I chose p to be 7

now we have 2^9 + 3(2^7) = 896
so length of x=9, length of y = 7
total is 16.

How do we knowthat it is the maximum?

we need not know.. because, the only other answer that is available is 18.
at the worst case, we can split it into power of x + power of y = 18
atleast one power should be greater than 9.
which is not possible even with the least prime number 2.
2^9 +3*2^9 ???

Hence pick D.

Last edited by kvcpk on Mon Jul 05, 2010 10:24 am, edited 1 time in total.

Like this post

selango: Legendary Member; Posts: 1460; Joined: Tue Dec 29, 2009 1:28 amFollowed by: 7 members; Thanked: 135 times

by selango » Mon Jul 05, 2010 7:05 am

the maximum number of prime multiples that can be accommodated is when the number has more 2 multiples.

I didn't think this way.Got it.Thanks.

--Anand--

Like this post

kvcpk: Legendary Member; Posts: 1893; Joined: Sun May 30, 2010 11:48 pmFollowed by: 7 members; Thanked: 215 times

by kvcpk » Mon Jul 05, 2010 7:12 am

selango wrote:the maximum number of prime multiples that can be accommodated is when the number has more 2 multiples.

I didn't think this way.Got it.Thanks.

Glad that it was helpful!!

Like this post

raunakrajan: Senior | Next Rank: 100 Posts; Posts: 62; Joined: Tue Mar 16, 2010 8:27 am; Thanked: 1 times

by raunakrajan » Mon Jul 05, 2010 9:56 am

kvcpk wrote:Hi Anand,

The wording of the problem is very difficult.

I will expalin How I approached the problem. Others can suggest even better ways.

Given x + 3y < 1000
Now the number of prime factors need to be maximum for both x and y.

Logically, the maximum number of prime multiples that can be accommodated is when the number has more 2 multiples.

So, I took x to be some power of 2.

Let us say 2^10 ->1024 INSUFFICIENT.
2^9 = 512 -> We still need to find y
now 512 + 3(2^p) <1000
3(2^p)<488
2^p<162

So I chose p to be 7

now we have 2^9 * 3(2^7) = 896
so length of x=9, length of y = 7
total is 16.

How do we knowthat it is the maximum?

we need not know.. because, the only other answer that is available is 18.
at the worst case, we can split it into power of x + power of y = 18
atleast one power should be greater than 9.
which is not possible even with the least prime number 2.
2^9 +3*2^9 ???

Hence pick D.

i still din get itt

can you explain it probably in a simpler way if possible!>?

Like this post

singhpreet1: Senior | Next Rank: 100 Posts; Posts: 95; Joined: Tue Jun 08, 2010 11:27 am; Thanked: 7 times

by singhpreet1 » Mon Jul 05, 2010 10:22 am

kvcpk wrote:Hi Anand,

The wording of the problem is very difficult.

I will expalin How I approached the problem. Others can suggest even better ways.

Given x + 3y < 1000
Now the number of prime factors need to be maximum for both x and y.

Logically, the maximum number of prime multiples that can be accommodated is when the number has more 2 multiples.

So, I took x to be some power of 2.

Let us say 2^10 ->1024 INSUFFICIENT.
2^9 = 512 -> We still need to find y
now 512 + 3(2^p) <1000
3(2^p)<488
2^p<162

So I chose p to be 7

now we have 2^9 * 3(2^7) = 896
so length of x=9, length of y = 7
total is 16.

How do we knowthat it is the maximum?

we need not know.. because, the only other answer that is available is 18.
at the worst case, we can split it into power of x + power of y = 18
atleast one power should be greater than 9.
which is not possible even with the least prime number 2.
2^9 +3*2^9 ???

Hence pick D.

i think u need to make a correction:

now we have 2^9 * 3(2^7) = 896

u mean 2^9 +3(2^7)= 896

i hope this was not causing any confusion to anyone.

Preet

Like this post

kvcpk: Legendary Member; Posts: 1893; Joined: Sun May 30, 2010 11:48 pmFollowed by: 7 members; Thanked: 215 times

by kvcpk » Mon Jul 05, 2010 10:26 am

@preet - Thanks for the correction.. That was a typo..Edited it now..

@raunakrajan - Can you please tell me till what point you understood it.. I can help you out.

Like this post

singhpreet1: Senior | Next Rank: 100 Posts; Posts: 95; Joined: Tue Jun 08, 2010 11:27 am; Thanked: 7 times

by singhpreet1 » Mon Jul 05, 2010 10:37 am

raunakrajan wrote: i still din get itt
can you explain it probably in a simpler way if possible!>?

Raunak..let me try and have a go and rephrase what has already been stated by kvcpk

lets look at the question again:

For any integer k > 1, the term Ã¢â‚¬Å“length of an integerÃ¢â‚¬Â� refers to the number of positive prime factors, not necessarily distinct, whose product is equal to k. For example, if k = 24, the length of k is equal to 4, since 24 = 2 X 2 X 2 X 3. If x and y are positive integers such that x > 1, y > 1, and x + 3y < 1000, what is the maximum possible sum of the length of x and the length of y?

A.5
B.6
C.15
D.16
E.18

so we know that both x and y are greater than 1. lets assume x=2, as we have to find the maximum possible length of x and y.
also 2 is the first prime number right? so if we take 2^10 then we get 1024 which does not satisfy the condition x + 3y < 1000.

ok, so lets assume x= 2^9= 512 yea?
now, again as per the condition to find y; x + 3y < 1000; y must be multiplied by 3 yea? so 3y= 3(2^7)= 384, why did i choose 2^7, if i take 2^8= 256, my condition of x + 3y < 1000 will not be satisfied, x= 512+3(256)= 1280 which is not less than 1000, so if i take x=2^9, y= 3(2^7)

i get 512+ 384= 896 which is less than 1000.

so, in 896 the prime factors used to determine x and y are: 9 2's (2^9) and 7 2's (2^7). lets add them up 9+7= 16.

i hope this was helpful to you.

Preet

Like this post

kvcpk: Legendary Member; Posts: 1893; Joined: Sun May 30, 2010 11:48 pmFollowed by: 7 members; Thanked: 215 times

by kvcpk » Mon Jul 05, 2010 10:43 am

singhpreet1 wrote: ok, so lets assume x= 2^9= 512 yea?
now, again as per the condition to find y; x + 3y < 1000; y must be multiplied by 3 yea? so 3y= 3(2^6)= 384, why did i choose 2^6, if i take 2^7= 256, my condition of x + 3y < 1000 will not be satisfied, x= 512+3(256)= 1280 which is not less than 1000, so if i take x=2^9, y= 3(2^6)

OOps.. typo..

2^7 = 128
so 512 + 3(128) = 896

2^8 = 256

Like this post

raunakrajan: Senior | Next Rank: 100 Posts; Posts: 62; Joined: Tue Mar 16, 2010 8:27 am; Thanked: 1 times

by raunakrajan » Mon Jul 05, 2010 1:01 pm

singhpreet1 wrote:
raunakrajan wrote: i still din get itt
can you explain it probably in a simpler way if possible!>?
Raunak..let me try and have a go and rephrase what has already been stated by kvcpk

lets look at the question again:

For any integer k > 1, the term Ã¢â‚¬Å“length of an integerÃ¢â‚¬Â� refers to the number of positive prime factors, not necessarily distinct, whose product is equal to k. For example, if k = 24, the length of k is equal to 4, since 24 = 2 X 2 X 2 X 3. If x and y are positive integers such that x > 1, y > 1, and x + 3y < 1000, what is the maximum possible sum of the length of x and the length of y?

A.5
B.6
C.15
D.16
E.18

so we know that both x and y are greater than 1. lets assume x=2, as we have to find the maximum possible length of x and y.
also 2 is the first prime number right? so if we take 2^10 then we get 1024 which does not satisfy the condition x + 3y < 1000.

ok, so lets assume x= 2^9= 512 yea?
now, again as per the condition to find y; x + 3y < 1000; y must be multiplied by 3 yea? so 3y= 3(2^7)= 384, why did i choose 2^7, if i take 2^8= 256, my condition of x + 3y < 1000 will not be satisfied, x= 512+3(256)= 1280 which is not less than 1000, so if i take x=2^9, y= 3(2^7)

i get 512+ 384= 896 which is less than 1000.

so, in 896 the prime factors used to determine x and y are: 9 2's (2^9) and 7 2's (2^7). lets add them up 9+7= 16.

i hope this was helpful to you.

Preet

thanks a ton boss! really helpful

Like this post

Post new topic Post Reply

• Page 1 of 1

GMAT Course Reviews

559 reviews

1168 reviews

431 reviews

359 reviews

147 reviews

5/5

5 Star (560 Reviews)

"Target Test Prep is the closest to the official version of the GMAT exam, about 99% accuracy in terms of the quality and quantity of information. The course has excellently created singular sets of focused lessons and tests for every possible topic that one could come across in the official GMAT exam."

"The TTP course maximizes the efficiency of the time you spend studying. It will take time and effort but I could almost guarantee that if you complete the course exactly as it is laid out you will get an amazing score. They also have a very responsive team willing to help with any questions you might have."

"TTP has two things that I think no other test prep company offers: A teaching approach that reinforces understanding and an attitude that will give you the mental preparedness needed to succeed on the test. TTP gives you a deep understanding of the concept you need to know while teaching you how to think."

Write a Review