The night before last, a member of a WeChat group posed the following question:
For any arbitrary integer N > 100, find an approximate algorithm to represent N = a \times b + c (where a, b, c are non-negative integers) such that a + b + c is as small as possible.
At first glance, my initial reaction was, "Does this even need an algorithm?" It seemed like there was so much freedom that an analytical solution should exist. After a brief analysis, I provided an "answer," but another group member quickly provided a counterexample. It was then that I realized the problem was not so trivial. After a formal derivation, I finally obtained a viable algorithm. Just as I thought the matter was settled, a member of another mathematics group elegantly constructed a new parameterization, proving that the complexity of the algorithm could be reduced even further!
The entire process was full of twists and turns, and I learned a great deal from it. I have recorded the process here to share with everyone.
A Casual Mistake
Setting aside the constraint N > 100, the original problem can be equivalently transformed into:
Given a, b \in \mathbb{N} and ab \leq N, find the minimum value of S = N - ab + a + b.
Clearly, when N is sufficiently large, the term ab should dominate. Intuitively, ab should be as close to N as possible, and a, b should be as close to each other as possible. Thus, I hastily suggested choosing between "a = b = \lfloor\sqrt{N}\rfloor" and "a = \lfloor\sqrt{N}\rfloor, b = \lfloor\sqrt{N}\rfloor + 1." However, a group member soon provided a counterexample: when N = 130, the minimum value of S is achieved at a = 10, b = 13, whereas my formula would give a = b = 11, which is clearly not optimal.
Upon further reflection, I realized I had underestimated the problem, so I began a serious derivation.
Direct Analysis
Without loss of generality, let a \leq b. First, S can be equivalently transformed into: \begin{equation} S = N - (\sqrt{ab}-1)^2 + (\sqrt{a}-\sqrt{b})^2 \end{equation} It can be seen that minimizing S generally involves two directions: 1. making ab as large as possible (close to N); 2. making a and b as close as possible. To this end, let us temporarily set: \begin{equation} b = \left\lfloor\frac{N}{a}\right\rfloor = \frac{N}{a} - \left\{\frac{N}{a}\right\} \end{equation} Then: \begin{equation} S = N - a\left(\frac{N}{a} - \left\{\frac{N}{a}\right\}\right) + a + \frac{N}{a} - \left\{\frac{N}{a}\right\} = (a-1)\left\{\frac{N}{a}\right\} + a + \frac{N}{a} \label{eq:S} \end{equation} Consider two extremes:
In the most ideal case, \{N/a\} = 0, then the minimum of a + N/a is reached at a = \sqrt{N}.
In the least ideal case, \{N/a\} can be infinitely close to 1, i.e., \begin{equation} S \to a - 1 + a + \frac{N}{a} = 2a + \frac{N}{a} - 1 \end{equation} In this case, the minimum is reached at a = \sqrt{N/2}.
Based on these two points, we can propose an algorithm:
Iterate a through all integers in the interval \big(\sqrt{N/2}, \sqrt{N}\big], let b = \lfloor N/a \rfloor, and select the one that minimizes S.
Clearly, this is an algorithm with complexity \mathcal{O}(\sqrt{N}), which is the same complexity as large integer factorization. I was quite shocked when I first derived this; such an unassuming problem turned out to have the same complexity as factorization.
New Parameterization
Later, I shared the problem in a mathematics group. Under the guidance of an expert there, I discovered that my previous analysis was still too superficial. It turns out the complexity of the algorithm can be significantly reduced.
The key to reducing complexity is introducing a new parameterization and using precise inequality bounds to narrow the search range. Suppose a and b have the same parity. We can set a = x - y and b = x + y, where x, y \in \mathbb{N}. Then we have: \begin{equation} N + y^2 = x^2 + c, \quad S = 2x + c \end{equation} The key to this new parameterization is changing the product ab into the difference x^2 - y^2, which allows us to see the direction of change more clearly and permits finer bounding. If a and b have different parities, we simply replace x with x + \frac{1}{2} and y with y + \frac{1}{2}. The derivation is similar, and we will discuss them separately.
Same Parity
Furthermore, we have: \begin{equation} S = 2x + c = 2x + (N + y^2 - x^2) = N + y^2 + 1 - (x - 1)^2 \end{equation} and N + y^2 \geq x^2. If x is fixed, then naturally S is minimized when y is minimized. Next, we discuss two cases.
The first case is x^2 \leq N. Then y^2 \geq x^2 - N, and the minimum value is clearly y = 0. In this case, S = N + 1 - (x - 1)^2. Obviously, S decreases as x increases. Given x^2 \leq N, the maximum possible value is x = \lfloor \sqrt{N} \rfloor.
The second case is x^2 \geq N. Then the minimum value of y^2 \geq x^2 - N is y = \lceil \sqrt{x^2 - N} \rceil. At this point: \begin{equation} \begin{aligned} S &= 2x + (N + y^2 - x^2) \\ &\leq 2x + \left[N + \left(\sqrt{x^2 - N} + 1\right)^2 - x^2\right] \\ &= 2x + 1 + 2\sqrt{x^2 - N} \end{aligned} \label{eq:S1} \end{equation} The final expression is monotonically increasing with respect to x. To make it as small as possible, x should be as small as possible. Given x^2 \geq N, we take x = \lceil \sqrt{N} \rceil. Note that this is calculated based on the upper bound of S. The actual minimum of S might not be at x = \lceil \sqrt{N} \rceil, but we can use this result to narrow the search range. Substituting this back into the inequality, we get: \begin{equation} \begin{aligned} S &\leq 2x + 1 + 2\sqrt{x^2 - N} \\ &\leq 2(\sqrt{N}+1) + 1 + 2\sqrt{(\sqrt{N}+1)^2 - N} \\ &= 2\sqrt{N} + 3 + 2\sqrt{1 + 2\sqrt{N}} \end{aligned} \label{eq:S2} \end{equation} This provides an upper bound for the minimum value of S. Suppose S reaches its minimum at x = x^*, c = c^*. Then: \begin{equation} \begin{array}{c} S = 2x^* + c^* \leq 2\sqrt{N} + 3 + 2\sqrt{1 + 2\sqrt{N}} \\ \Downarrow \\ x^* \leq \sqrt{N} + \frac{3}{2} + \sqrt{1 + 2\sqrt{N}} = \sqrt{N} + \mathcal{O}(\sqrt[4]{N}) \end{array} \end{equation} This means we only need to search for integers in the range \big[\sqrt{N}, \sqrt{N} + \frac{3}{2} + \sqrt{1 + 2\sqrt{N}}\big] to find the optimal solution. The complexity is \mathcal{O}(\sqrt[4]{N}) instead of \mathcal{O}(\sqrt{N})!
Different Parity
Suppose a and b have different parities. We can set a = (x + \frac{1}{2}) - (y + \frac{1}{2}) and b = (x + \frac{1}{2}) + (y + \frac{1}{2}), where x, y \in \mathbb{N}. Then: \begin{equation} \begin{aligned} &N + \left(y + \frac{1}{2}\right)^2 = \left(x + \frac{1}{2}\right)^2 + c \\ &S = 2\left(x + \frac{1}{2}\right) + c = N + \left(y + \frac{1}{2}\right)^2 + 1 - \left(x - \frac{1}{2}\right)^2 \end{aligned} \end{equation} Again, we discuss two cases. First, when (x + \frac{1}{2})^2 \leq N, similar to the previous section, the result is y = 0 and x = \lfloor \sqrt{N} - \frac{1}{2} \rfloor. Second, when (x + \frac{1}{2})^2 \geq N, the minimum value of y is y = \lceil \sqrt{(x + \frac{1}{2})^2 - N} - \frac{1}{2} \rceil. Following the same logic as equations [eq:S1] and [eq:S2], substituting x = \lceil \sqrt{N} - \frac{1}{2} \rceil, we have: \begin{equation} \begin{aligned} S &= 2\left(x + \frac{1}{2}\right) + \left[N + \left(y + \frac{1}{2}\right)^2 - \left(x + \frac{1}{2}\right)^2\right] \\ &\leq 2\left(x + \frac{1}{2}\right) + \left[N + \left(\sqrt{\left(x + \frac{1}{2}\right)^2 - N} + 1\right)^2 - \left(x + \frac{1}{2}\right)^2\right] \\ &= 2\left(x + \frac{1}{2}\right) + 1 + 2\sqrt{\left(x + \frac{1}{2}\right)^2 - N} \\ &\leq 2(\sqrt{N} + 1) + 1 + 2\sqrt{(\sqrt{N} + 1)^2 - N} \\ &= 2\sqrt{N} + 3 + 2\sqrt{1 + 2\sqrt{N}} \end{aligned} \end{equation} Therefore: \begin{equation} \begin{array}{c} S = 2(x^* + \frac{1}{2}) + c^* \leq 2\sqrt{N} + 3 + 2\sqrt{1 + 2\sqrt{N}} \\ \Downarrow \\ x^* \leq \sqrt{N} + 1 + \sqrt{1 + 2\sqrt{N}} = \sqrt{N} + \mathcal{O}(\sqrt[4]{N}) \end{array} \end{equation}
Summary of Results
Combining the results of the above two sections, we can organize the process for finding the minimum value of S as follows:
If N is a perfect square, return x = \sqrt{N}, y = 0 (i.e., a = b = \sqrt{N}, c = 0).
Otherwise, record the pair (x, y) that yields the smaller S between (x = \lfloor \sqrt{N} \rfloor, y = 0) and (x = \lfloor \sqrt{N} - \frac{1}{2} \rfloor + \frac{1}{2}, y = \frac{1}{2}).
Iterate through all integers m in the range \big(\sqrt{N} - 1/2, \sqrt{N} + \frac{3}{2} + \sqrt{1 + 2\sqrt{N}}\big]. Let x = m, y = \lceil \sqrt{m^2 - N} \rceil and x = m + \frac{1}{2}, y = \lceil \sqrt{(m + \frac{1}{2})^2 - N} - \frac{1}{2} \rceil + \frac{1}{2}. If either corresponds to a smaller S, update the recorded x, y.
Return a = x - y, b = x + y, c = N - ab.
Another Perspective
After the article was published, another expert felt that the discussion of parity was too cumbersome and proposed a new parameterization: let p = a + b and q = b - a. Then: \begin{equation} 4N - p^2 + q^2 = 4c, \quad S = p + c \end{equation} Note that p and q must have the same parity to ensure that c is an integer.
The subsequent analysis is almost identical. Since c \geq 0, we have q^2 \geq p^2 - 4N. For a given p, minimizing S is equivalent to minimizing c, which is equivalent to minimizing q. If p^2 \leq 4N, the minimum value of q is 0 or 1, determined by the parity of p. Then, according to: \begin{equation} 4S = 4p + 4c = 4p + 4N - p^2 + q^2 = 4N + q^2 + 4 - (p - 2)^2 \end{equation} minimizing S corresponds to maximizing p. Given p^2 \leq 4N, we have p = \lfloor 2\sqrt{N} \rfloor.
If p^2 \geq 4N, the minimum value of q is q = \lceil \sqrt{p^2 - 4N} \rceil + \varepsilon, where \varepsilon \in \{0, 1\} is chosen to ensure p and q have the same parity. Substituting this in: \begin{equation} \begin{aligned} 4S &= 4p + 4N - p^2 + q^2 \\ &\leq 4p + 4N - p^2 + \left( \sqrt{p^2 - 4N} + \varepsilon + 1\right)^2 \\ &= 4p + (\varepsilon + 1)^2 + 2(\varepsilon + 1)\sqrt{p^2 - 4N} \end{aligned} \end{equation} Substituting p = \lceil 2\sqrt{N} \rceil, we can derive an upper bound for the minimum value of 4S: \begin{equation} \begin{aligned} 4S &\leq 4p + (\varepsilon + 1)^2 + 2(\varepsilon + 1)\sqrt{p^2 - 4N} \\ &\leq 4(2\sqrt{N} + 1) + (\varepsilon + 1)^2 + 2(\varepsilon + 1)\sqrt{(2\sqrt{N} + 1)^2 - 4N} \\ &= 4(2\sqrt{N} + 1) + (\varepsilon + 1)^2 + 2(\varepsilon + 1)\sqrt{1 + 4\sqrt{N}} \\ &\leq 4(2\sqrt{N} + 1) + 4 + 4\sqrt{1 + 4\sqrt{N}} \\ \\ &\Rightarrow S \leq 2\sqrt{N} + 2 + \sqrt{1 + 4\sqrt{N}} \end{aligned} \end{equation} Since S = p + c \geq p, this is also an upper bound for p.
In summary, the new process for finding the minimum S is as follows:
If N is a perfect square, return p = 2\sqrt{N}, q = 0 (i.e., a = b = \sqrt{N}, c = 0).
Otherwise, let p = \lfloor 2\sqrt{N} \rfloor. If p is even, set q = 0; otherwise, set q = 1. Calculate the corresponding S.
Iterate through all integers p in the range \big(2\sqrt{N}, 2\sqrt{N} + 2 + \sqrt{1 + 4\sqrt{N}}\big]. Let q = \lceil \sqrt{p^2 - 4N} \rceil + \varepsilon, where \varepsilon \in \{0, 1\} ensures p and q have the same parity. If the resulting S is smaller, update the recorded p, q.
Return a = \frac{p-q}{2}, b = \frac{p+q}{2}, c = N - ab.
Conclusion
This article shares the thinking and learning process behind an algorithm problem that "seemed like a Bronze but turned out to be a Challenger."
Original link: https://kexue.fm/archives/9775
For more details on reprinting, please refer to: Scientific Space FAQ