1
$\begingroup$

For any positive integer P, is there a formula or an algorithm that can find the closest pair X of integers a and b, that multiplied together result in that integer P?

In other words: knowing P, find closest a and b that satisfy a * b = P

By closest I mean - the difference between a and b is smallest possible.


Square example: I have a number 256. I know, using square root, that a = 16 and b = 16 will be that pair X I'm looking for. For P being a square of any integer this is easy. How about for other integers?

Non-square example: if P = 198, I found that a = 11 and b = 18 is my pair X. This time however I had to go through trial and error (picking random numbers) to find my answer.

  • Is there any way I could calculate the pair X automatically?
  • Is there a name for the problem I'm describing?
  • Am I missing something (such as edge cases that can't be calculated)?

Context (feel free to ignore this): I'm working with images. Sometimes, the data is provided in a flattened format (as one row of numbers), and I'm trying to figure out how to unravel the data back to the image format of width x height (however please don't worry about whether I guess the correct dimensions of the original data - it's irrelevant). Therefore, having a and b closest to each other is needed in my use case.

$\endgroup$
  • $\begingroup$ I don't know if this comment will help you. Anyway, have you considered to use prime decomposition?. For example, $198=2\cdot 3 \cdot 3\cdot 11$. So your problem is reduced to find the best rearrangement: $(2\cdot 3\cdot 3)\cdot 11$. $\endgroup$ – Dog_69 Apr 8 '18 at 17:57
  • $\begingroup$ Thanks for suggesting! I'm not sure I understand it completely, but I'll look into prime decomposition. However, isn't your suggestion assuming that I know a=11? $\endgroup$ – Voy Apr 8 '18 at 17:59
  • $\begingroup$ No... Well, What I have tried to explain was if you know prime factors of $P=p_1\cdot p_2 \cdot \cdots \cdot p_n$, you ''only'' have to evaluate $n \choose 2$ posibilities (more or less): $(p_1)\cdot(p_2\cdot\cdots \cdot p_n)$ or $(p_1\cdotp_2)\cdot(p_3\cdot \cdots\cdot p_n)$ or... However, note I omiting possible powers $p_i^{a_i}$, which can make the problem more difficult (than I have assumed in this comment). $\endgroup$ – Dog_69 Apr 8 '18 at 18:04
  • $\begingroup$ I don't know what does ''trial and error'' mean for you. How have you found $11$ and $18$? Picking random numbers, for example $12$ and $18$, $15 $ and $21$, etc and then demonstrating their product is $198$ and finding which is the closest pair? $\endgroup$ – Dog_69 Apr 8 '18 at 18:09
  • 1
    $\begingroup$ I'm afraid there is probably no efficient algorithm in the general case. That would imply the ability to factor large semiprimes. $\endgroup$ – Patrick Stevens Apr 8 '18 at 18:20

Your Answer

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

Browse other questions tagged or ask your own question.