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

Redeem

Tough prime factorisation problem

This topic has expert replies
Post new topic Post Reply
Previous Topic Next Topic
User avatar
Legendary Member
Posts: 1460
Joined: Tue Dec 29, 2009 1:28 am
Thanked: 135 times
Followed by:7 members

Tough prime factorisation problem

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--
Top
Source: — Problem Solving |
User avatar
Legendary Member
Posts: 1893
Joined: Sun May 30, 2010 11:48 pm
Thanked: 215 times
Followed by:7 members

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.
Top
User avatar
Legendary Member
Posts: 1460
Joined: Tue Dec 29, 2009 1:28 am
Thanked: 135 times
Followed by:7 members

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--
Top
User avatar
Legendary Member
Posts: 1893
Joined: Sun May 30, 2010 11:48 pm
Thanked: 215 times
Followed by:7 members

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!! :)
Top
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!>?
Top
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
Top
User avatar
Legendary Member
Posts: 1893
Joined: Sun May 30, 2010 11:48 pm
Thanked: 215 times
Followed by:7 members

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.
Top
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
Top
User avatar
Legendary Member
Posts: 1893
Joined: Sun May 30, 2010 11:48 pm
Thanked: 215 times
Followed by:7 members

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
Top
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
Top
Post new topic Post Reply
• Page 1 of 1