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?
Tough prime factorisation problem
This topic has expert replies
- kvcpk
- Legendary Member
- Posts: 1893
- Joined: Sun May 30, 2010 11:48 pm
- Thanked: 215 times
- Followed by:7 members
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.
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.
-
- Senior | Next Rank: 100 Posts
- Posts: 62
- Joined: Tue Mar 16, 2010 8:27 am
- Thanked: 1 times
i still din get ittkvcpk 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.
can you explain it probably in a simpler way if possible!>?
-
- Senior | Next Rank: 100 Posts
- Posts: 95
- Joined: Tue Jun 08, 2010 11:27 am
- Thanked: 7 times
i think u need to make a correction: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.
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
-
- Senior | Next Rank: 100 Posts
- Posts: 95
- Joined: Tue Jun 08, 2010 11:27 am
- Thanked: 7 times
Raunak..let me try and have a go and rephrase what has already been stated by kvcpkraunakrajan wrote: i still din get itt
can you explain it probably in a simpler way if possible!>?
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
- kvcpk
- Legendary Member
- Posts: 1893
- Joined: Sun May 30, 2010 11:48 pm
- Thanked: 215 times
- Followed by:7 members
OOps.. typo..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)
2^7 = 128
so 512 + 3(128) = 896
2^8 = 256
-
- Senior | Next Rank: 100 Posts
- Posts: 62
- Joined: Tue Mar 16, 2010 8:27 am
- Thanked: 1 times
thanks a ton boss! really helpfulsinghpreet1 wrote:Raunak..let me try and have a go and rephrase what has already been stated by kvcpkraunakrajan wrote: i still din get itt
can you explain it probably in a simpler way if possible!>?
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