# How to find the most square-ish factorization of an integer?

Given an integer $$n\in\Bbb N$$, what's the best (known) way to decompose it as the product of two integers in such a way that the factors are the sides of a rectangle that's as close as possible to a square? The full factorization of $$n$$ into prime factors can be assumed to be known if that's helpful.

More formally:

Given $$n\in \Bbb N$$, find a divisor $$d|n$$ such that $$|d-n/d| \stackrel{!}= \min$$.

or

Given $$n\in \Bbb N$$, find $$a, b\in\Bbb N$$ such that $$a\cdot b=n$$ and $$a+b \stackrel{!}= \min$$.

Using the factorization $$n = \displaystyle \prod_{j=1}^k p_j$$ where primes might occur more than once, this can be restated using logarithms:

Find $$k$$ values $$b_j\in\{-1,1\}$$ such that $$\displaystyle \Bigg|\sum_{j=1}^k b_j\log p_j \Bigg|\stackrel{!}= \min$$.

This looks like a knapsack problem which are known to be hard in general. For $$n > 1$$ there are $$2^{k-1}$$ possible decompositions into different pairs of factors, and checking all of them is expensive when $$n$$ has many factors. Moreover:

If someone comes up with a specific decomposition asserting it's the most square-ish one: Is it easier to check whether the solution is correct, or is it as expensive as determining the best solution in the first place?

As an example, let $$H_D(x)\in \Bbb Z[x]$$ be the Hilbert class polynomial for discriminant $$D$$ and let $$n=H_{-71}(0)$$: $$n = 737707086760731113357714241006081263 = 11^9 \cdot 17^6 \cdot 23^3 \cdot 41^3 \cdot 47^3 \cdot 53^3$$

See . This $$n$$ has $$2^{26} = 67\,108\,864$$ different decompositions, which is doable with brute force on a modern computer. But is there a smarter approach?

Two more demanding test cases are

• $$H_{-119}(0) = (11^4 \cdot 17 \cdot 23^2 \cdot 29^2 \cdot 47 \cdot 59 \cdot 83 \cdot 89)^3$$ with $$2^{38}\approx 2.7\cdot 10^{11}$$ decompositions and

• $$H_{-907}(0) = (2^{19} \cdot 3^3 \cdot 5^3 \cdot 131 \cdot 137 \cdot 167)^3$$ with $$2^{83}\approx 9.7\cdot 10^{24}$$ decompositions.

## Note 1

As Jukka Kohonen mentions in a comment, the upper bound for the complexity of a brute-force approach can be reduced: Let $$n=\displaystyle\prod_{i=1}^m p_i^{e_i}$$ with pairwise different primes $$p_i$$ be the factorization of $$n$$. Then the task is:

Find $$m$$ integers $$a_i$$ with $$0\leqslant a_i \leqslant e_i$$ such that $$\Bigg|\log n - 2\displaystyle \sum_{i=1}^m a_i\log p_i \Bigg| \stackrel!= \min$$.

If all $$a_i$$ are replaced by $$e_i-a_i$$ then the value to be minimized stays the same.

1. If all $$e_i$$ are even, then $$n$$ is a perfect square and the solution is clear.
2. If at least one $$e_i$$ is odd, then a brute-force approach has to test $$\dfrac12\displaystyle\prod_{i=1}^m (1+e_i)$$ combinations of the $$a_i$$.

The examples above are all in case 2., and the corrected number of tries are:

• $$H_{-71}(0)$$: $$\frac12\cdot 10 \cdot 7 \cdot 4 \cdot 4 \cdot 4 \cdot 4 = 8960$$ possibilities.

• $$H_{-119}(0)$$: $$\frac12\cdot 13 \cdot 4 \cdot 7 \cdot 7 \cdot 4 \cdot 4 \cdot 4 \cdot 4 = 326144$$ possibilities.

• $$H_{-907}(0)$$: $$\frac12\cdot 58 \cdot 10 \cdot 10 \cdot 4 \cdot 4 \cdot 4 = 185600$$ possibilities.

## Conclusion:

The work that's needed to get the complete factorization of $$n$$ is in general much higher than brute-force checking which pair of divisors is the best choice.

Related:

• I think you are slightly overestimating the brute force workload. Given $n=11^9 \cdot 17^6 \cdot 23^3 \cdot 41^3 \cdot 47^3 \cdot 53^3 = ab$, you want to divide the nine 11's between the factors (10 choices), same for the six 17's (7 choices) etc. so $10 \cdot 7 \cdot 4 \cdot 4 \cdot 4 \cdot 4 = 17920$ decompositions, not $67108864$. (And divide by two because you can assume $a$ has fewer 11's than $b$.) Sep 7, 2021 at 10:50
• @Jukka Kohonen: You are right, thanks. I will edit my question, but it will take some hours til I'm back. Sep 7, 2021 at 11:22
• Ok. For the record, the most-square factorization for $H_{-907}(0)$ seems to be $386208961375062977740800 \cdot 386219092937277440000000$, by brute-force SageMath code in 23 seconds, so you'll want to create more demanding test cases. Sep 7, 2021 at 11:33
• As long as we can enumerate over the divisors of the given number, the problem can be done by brute force. And I highly doubt that there is a better method in general. Note that you do not need to enumerate all decompositions. It is sufficient to know all the divisors. Your last example still has only $371\ 200$ divisors. This is no challenge whatsoever. Sep 7, 2021 at 13:38
• In fact the first $H$ is a harder instance, but still far from being a challenge. Sep 7, 2021 at 13:46

Equivalently, you want to minimize the larger of the two factors. Given the prime factorization $$\prod_{i=1}^m p_i^{e_i}$$, you can solve the problem via integer linear programming as follows. Let integer decision variable $$x_i$$ denote the number of times that $$p_i$$ appears in the first factor, so that the two factors are $$\prod_{i=1}^m p_i^{x_i}$$ and $$\prod_{i=1}^m p_i^{e_i-x_i}$$. The problem is to minimize $$z$$ subject to \begin{align} \sum_{i=1}^m \log(p_i) x_i &\le z \tag1 \\ \sum_{i=1}^m \log(p_i) (e_i-x_i) &\le z \tag2 \\ 0 \le x_i &\le e_i &&\text{for i\in\{1,\dots,m\}} \tag3 \end{align} Constraints $$(1)$$ and $$(2)$$ enforce the minimax objective. Constraint $$(3)$$ enforces the factorization.
All three test cases solve instantly. For the third one, an optimal solution is $$x=(16, 9, 2, 0, 3, 3)$$, which agrees with @Jukka Kohonen.