TITLE: What is the smallest positive difference between two integers whose product is $2400$?
QUESTION [2 upvotes]: What is the smallest positive difference between two integers whose product is $2400$?

I just tried factorizing $2400 = 2*1200 = 4*600=8*300=\cdots$ and testing different pairs, but this is a slow and unreliable way of doing this question. What is the best way and fastest to do this question?

REPLY [1 votes]: One of the fastest methodolical ways seem to be to use prime factorization of the number (finding them need you in worst case to test factors up to $\sqrt{2400}$ though):
$$2400 = 2^5\cdot3\cdot5^2$$
and then find the largest factor less than or equal to $\sqrt{2400}$ which turns out to be $48 = 2^4\cdot3$ and the other is therefore $2\cdot5^2=50$. This relies on the fact that the factors must be one that is at most $\sqrt{2400}$ and the other at least $\sqrt{2400}$. Using brute force means that you have to search through $36 = (1+5)(1+1)(1+2)$ combinations of $2^j3^k5^l$. But there are some tricks that would reduce the number of tries one is to use monotonicity and not check lower $j$s, $k$s or $l$s once you've found a combo less than $\sqrt{2400}$ or opposite for a combo larger than $\sqrt{2400}$. I similar trick is to find the closest of one of the exponents given the two others which reduce the number of combos to just $6 = (1+1)(1+2)$ (select $k$ and $l$ and deduce $j$ from that, but you'd have two candidates in general for $j$, one giving result below $\sqrt{2400}$ and one above, but one could quite easily deduce which one is nearest). A third trick is to notice that one of the factors must have the factor $3$ and searching for that includes only scanning through $j$s and $k$s and combined with the second trick that means that you only have to consider three cases ($l$ being $0$, $1$ or $2$):
$$2^j\cdot3\cdot5^0 = 2^j15 = \sqrt{2400}\rightarrow j=\log_2{\sqrt{2400}\over3}\approx 4.03$$
$$2^j\cdot3\cdot5^0 = 2^j15 = \sqrt{2400}\rightarrow j=\log_2{\sqrt{2400}\over15}\approx 1.71$$
$$2^j\cdot3\cdot5^0 = 2^j15 = \sqrt{2400}\rightarrow j=\log_2{\sqrt{2400}\over75}\approx -0.61$$
It's obvious which integer $j$ becomes nearest, so we get three candidates:
$$2^4\cdot3\cdot5^0 = 48$$
$$2^2\cdot3\cdot5^1 = 60$$
$$2^0\cdot3\cdot5^2 = 75$$
here we see that closest to $\sqrt{2400}$ is $48$ so one factor is $48$ and 
therefore the other is $50 = 2400/48$.
Another solution is to again use the fact that one factor is at most $\sqrt{2400}$ and then test with all alternatives less than or equal to $\sqrt{2400}$. In this case you would have to test $48$ candidates starting from $48$ and working downwards until you find a solution. In this case it terminates quickly as you find the solution at once. 
The first method requires as mentioned to first prime factor the number which would in worst case require $\sqrt{2400}$ steps, but for each prime factor that is found the number of steps required to prime factor it would drop. The worst case scenario for that algorithm is if you're considering the product of two prime twins, for example $1763=41\cdot43$ where the second algorithm would win big time. On the other hand when you have small prime factors and still quite a difference the first method would be better, for example $2048=2^{11}$ would be prime factored in just eleven steps, and the solution would be found immediately as $2048 = 32\cdot64$ while the second method would need to try $45, 44, \cdots, 32$ (fourteen steps).
{"set_name": "stack_exchange", "score": 2, "question_id": 1616251}