Prime Factors

[surajgarg]

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=2x2x2x3. 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

[outreach]

first tried to find the maximum number possible with 2 as prime=512=2^9
now y has to be less than (1000-512)/3=166

y=160=2^5*5^1

max length possible 9+6=15

[kmittal82]

Hmm, I got (C) as the answer, but Ill share my method anyways.

x + 3y < 1000

The maximum length will be when all the factors are 2, so essentially we need to find perfect squares of 2.

Now, give the above, the maximum value of y we can have is 256 (any number higher than 256 will violate the inequality)

y = 256 = 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 -> Length = 8

This gives the maximum value of x as 231. The closes perfect square to that with maximum length (i.e. all factors 2) is 128 = 2 x 2 x 2 x 2 x 2 x 2 x 2 -> Length = 7

Total maximum length = 15

Not the same answer as the OA, but I would like to know where I have gone wrong.

Thanks

[surajgarg]

Hey thanks for the approach. I was unable to understand how to approach this.

The answer is indeed D. 16

x+3y<1000

In such a case x has to be maximum possible power of 2 which turns out to be 512, which implies no. of prime factors is 9
So y will be 128, no. of prime factors is 7

So sum is 16!!!

[kmittal82]

Hey thanks for the approach. I was unable to understand how to approach this.

The answer is indeed D. 16

x+3y<1000

In such a case x has to be maximum possible power of 2 which turns out to be 512, which implies no. of prime factors is 9
So y will be 128, no. of prime factors is 7

So sum is 16!!!

Ah, I got the wrong end of the stick here, shouldv'e maximized x instead of y

Thanks for the solution, good question

[outreach]

mmm..
maximizing factors of 2 for both x and y then gives the solution

[sumanr84]

first tried to find the maximum number possible with 2 as prime=512=2^9
now y has to be less than (1000-512)/3=166

y=160=2^5*5^1

max length possible 9+6=15

Nice approach by outreach..thanks

This signifies how even after knowing the root of the problem mistakes can happen.

[sanju09]

good question surajgarg, liked the trap very much

[kvcpk]

I rememeber doing this problem earlier and was searching for this link from past 15 mins..

Here you go..

https://www.beatthegmat.com/tough-prime- ... tml#270083

[selango]

This is one of the MGMAT CAT problem.

[aleph777]

I just want to confirm the strategy here.

When it came to solving for x, I immediately went looking for the max exponent of 2.

x = 512 = 2^9

I messed up with solving for y, though, because I just looked for the prime factors of 162 rather than an exponential series of 2s.

PRIME FACTORS of 162: 2 x 3 x 3 x 3 x 3
EXPONENTS OF 2: 2 x 2 x 2 x 2 x 2 x 2 x 2

So my problem was not continuing to search for an exponential value as I did when solving for x.

When it comes to this sort of question (max. length of integers), it seems that you should ALWAYS work with the smallest possible integer, correct?

Thanks!