Tough prime factorisation problem

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 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.

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!!

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!>?

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

@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.

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

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

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