Lengthy numbers

[singh_na]

Hi All,

I am having a hard time trying to understand this problem.I would really appreciate any help.

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?

5
6
15
16
18

Thanks
SN

[tlien]

The question is basically asking what is the total number of prime numbers in 1000.

1000= 2^3*5^3

so....total prime number is 6.

Since the question stated that x+3y<1000, we have to subtract 1 from 6.

Thus, answer is 5.

I think you can eliminate 15, 16, and 18, because 2 (smallest prime number) to the 15th power is way more than 1000 and same with 16 and 18.

Please correct me if I made a mistake.

Eric

[poojakrishnamurthy1]

I don't think the answer is 5. Infact it should be 16.

The number of prime factors would be maximum when both x=y=2 , which is the smallest prime number.

So x + 3y < 1000 could be written as -

512 + 3x128 < 1000 OR

2^9 + 3 x 2^7 < 1000

The length here would be 9+7=16.

Thus the answer should be 16.

Let me know the OA.

[tlien]

poojakrishnamurthy1@gmail:

I like your method, but should the answer be 17? Since you are mutiplying 3 in the y term. Anyway, now you pointed it out, I am not sure how to solve it, haha, but OA would be nice though.


Eric

[poojakrishnamurthy1]

poojakrishnamurthy1@gmail:

I like your method, but should the answer be 17? Since you are mutiplying 3 in the y term. Anyway, now you pointed it out, I am not sure how to solve it, haha, but OA would be nice though.


Eric

The question asks what is the maximum possible sum of the length of x and the length of y?

You have mistaken y to be "3 x 2^7" but that isn't correct.

Actually y = 2^7.

Similarly x = 2^9.

Thus the maximum possible sum of the length of x & y = 9+7=16.

Hope this helps. :-)

[esledge]

Looks like Eric and Pooja got this one worked out.

I want to emphasize the general principle Pooja mentioned: To maximize "length" (i.e. number of primes) subject to an upper limit (here, 1000 for the sum), minimize the prime bases themselves.

To quickly hone in on numbers to plug, you could write the following on paper:

2^(length of x) + 3 * 2^(length of y) < 1000, where the "length of..." might just be empty boxes that represent test numbers.

Then, you can look at the terms separately to find a maximum exponent for each individually:
2^10 = 1024>1000, so the (length of x) <= 9.
3*2^8 = 3*256 = 768 < 1000
3*2^9 = 3*512 = 1536 >1000, so the (length of y) <=8.

That rules out 18 as the sum of the lengths. If it had been listed, 17 would have been a bit of a trap answer. You would have to combine the terms to test those individual maximum exponents:
2^9 + 3*2^8 = 512 + 3*256 = 512 + 768 > 1000-->NO
2^9 + 3*2^7 = 512 + 3*128 = 512 + 384 < 1000-->OK

[andy.wy.tam]

Is there a shorter method to get the answer to this question?
I don't think I'd be able to do this question in 2 min on test day... there just seems to be too much going on!

[tim]

I'll make two observations here:

1) A lot of people could solve this one in two minutes, so it may be that you just aren't working quickly enough.

2) There is no rule that says EVERY question must be solved in two minutes or less, only that you must AVERAGE two minutes-ish on the questions.