# Number Theory: Prime Factors

A number greater than 5000 but less than 6000 has prime factors $2^x3^y5^z$ such that $x,y,z > 0$. A possible value of $x+y+z$ is:

a)5 b) 8 c)11 d)18

Not sure my approach is works.

• Possible values of x,y and z are 3,3 and 2. – N.S.JOHN Feb 27 '16 at 2:37
• Note that you factored $5500$ incorrectly. It is in fact $5500=2^2\cdot 5^3\cdot 11$. It is clear that $5500$ is not divisible by three since the sum of the digits is not divisible by three. – JMoravitz Feb 27 '16 at 2:59

Since we require at least one of each factor $2,3,5$, consider the problem instead as $5000\leq 2\cdot 3\cdot 5\cdot 2^{x'}\cdot 3^{y'}\cdot 5^{z'}\leq 6000$ where we drop the requirement that each $x',y',z'$ be strictly positive and we ask for a possible value of $x'+y'+z'+3$.

We have then $166.\overline{6}\leq 2^{x'}\cdot 3^{y'}\cdot 5^{z'}\leq 200$

Find a lower bound on $x'+y'+z'$ by noting that it will be minimized when $x'=y'=0$ and $z'$ is an appropriate size. $z'$ will need to be at least $\log_5(166.\overline{6})$, so

$$\log_5(166.\overline{6})\approx 3.1787\leq x'+y'+z'$$

Similarly in finding an upper bound on $x'+y'+z'$ note that it will be maximized when $y'=z'=0$ and $x'$ is an appropriate size. $x'$ will need to be at most $\log_2(200)$, so

$$x'+y'+z'\leq 7.6438\approx \log_2(200)$$

Thus $6.1787\leq x+y+z=x'+y'+z'+3\leq 10.6438$

Possible values then would be $7,8,9,10$, eliminating options $a,c$ and $d$.

It remains to show that $8$ is still possible, which can be verified via trial and error as $2^33^35^2=5400$

• Seems quite complicated. Why complicate it this much? This method cannot be followed when you are writing a test or something. – N.S.JOHN Feb 27 '16 at 3:48
• @n.s.john the values of the logarithms can easily be estimated by comparing to nearby powers of two and five respectively. $2^7=128$ and $2^8=256$ so the upper bound is above 7 but below 8 (before shifting by 3) and $5^3=125$ and $5^4=625$ so the lower bound is above 3 but below 4 (before shifting) – JMoravitz Feb 27 '16 at 4:05

We can get the answer from the options given. If we take $x+y+z=5$, then the max possible value is $5^3 ×2^1 ×3^1$ which is 750.

The min possible value for $x+y+z=11$ is $2^9 ×3^1 ×5^1$ is 7680.

So it can never be 18. The answer is 8.