3
$\begingroup$

Which three-digit number has the greatest number of different factors?

This question comes from an Olympiad, where four marks were given for the solution to this problem. The textbook lists an accepted answer as:

Let $N$ be the three-digit number which has the greatest number of different factors. Since $2\times3\times5\times7\times11>1000$, $N$ at most has four different prime factors.

If $N$ only has one prime factor, then $N=2^9$, and so $N$ has 10 different factors.

If $N$ has exactly two prime factors, then $N=2^5\times3^3$, and so $N$ has 24 different factors.

If $N$ has exactly three prime factors, then $N=2^4\times3^2\times5$, and so $N$ has 30 different factors.

If $N$ has exactly four prime factors, then $N=2^3\times3\times5\times7$, and so $N$ has 32 different factors.

Thus, $N=2^3\times5\times7=\bf840$.

What I don't understand is why $N=2^5\times 3^3$ when $N$ has two prime factors, and similarly why $N=2^3\times3\times5\times7$ when N has three factors. I think it has to do with the maximum 'arrangement' of factors such that $N$ has the most factors possible, but I don't understand how we can calculate that. Furthermore, could we solve a similar problem involving a four-digit number instead using the above method?

Thanks for any help you're able to provide. -Jazza

$\endgroup$
  • $\begingroup$ The number of factors is determined solely by the number of prime factors and to what power those primes are taken. However, the number of factors has nothing to do with what the actual values of the primes are. So $N=p^2q^3$ will have the same number of factors (12) whether $N$ is $3^22^3$ or if $N $ is $113^267^3$. The solution is assuming, without stating, that to get the most factors "bang for the buck", you take the smallest possible primes to the largest possible powers. $\endgroup$ – fleablood Aug 27 '17 at 4:28
  • $\begingroup$ @fleablood I think I partially understand - for a number with prime factorization $p_{1}^{e_1}\times p_{2}^{e_2}\times p_{3}^{e_3}\dots p_{x}^{e_k}$ the number of factors that number will have is equal to $(e_1+1)(e_2+1)(e_3+1)\dots (e_k+1)$. Thus, we want to have the highest possible product of that equation. However, what I'm wondering is how we want to go about finding the highest possible product. Is it something like 'divide by 2 until you reach threshold x'? What method would we use? $\endgroup$ – user472341 Aug 27 '17 at 4:39
  • $\begingroup$ Well, they are simply doing brute force. And AM-GM. Ex. For 3 primes you will have $2^k3^j5^m $ with $k\ge j \ge m $. k can be as high as $\log_2 1000/15$ or $6$. But then $j $ and $m $ will be 1. And the highest product will be the ones where k,j, and m are closest together. Trial and error shows we have $2^63*5$ or $2^4*3^2*5$ $\endgroup$ – fleablood Aug 27 '17 at 5:22
3
$\begingroup$

As the number must be $N<1000$ its prime factors must be $2\times 3\times 5 \times 7$ when it has two factors it makes no sense considering, for instance, $5^3\times 7$ which is $875$ less than $1000$ but has only $(3+1)(1+1)=8$ factors.

$2^3\times 5 $ is smaller and has the same number of divisors. The maximum number of divisors is attained when $N=2^a\times 3^b$. You can try and see that $d(N)=(a+1)(b+1)$ is maximum and $N<1000$ is the largest when $a=5;\;b=3$, that is $N=2^5\times 3^3= 864$ and $d(864)=6\times 4=24$.

In a similar way you can find the other results and solve the problem with $840=2^3\times5\times7$ which has $32$ divisors.

The issue is called Highly Composed Numbers and if you want to know more look here.

$\endgroup$
  • $\begingroup$ Thank you for sharing the link to Highly Composite Numbers, it answered my question of why we use the number 360 instead of a number like 420 or 840. $\endgroup$ – ray lin Jun 16 '18 at 18:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy