By 苏剑林 | September 20, 2023
The night before last, a member in a WeChat group posed a question: For an arbitrary integer $N > 100$, find an approximate algorithm to find $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, "Is an algorithm even necessary for this?" It seemed like there was so much freedom that an analytical solution should exist. After a brief analysis, I offered an "answer," but a group member quickly provided a counterexample. It was then that I realized the problem was not so trivial. After formally deriving it, I finally arrived at a viable algorithm. Just as I thought the problem was settled, a member of another mathematics group elegantly constructed a new parameterization, proving that the algorithm's complexity could be further reduced! The entire process was full of twists and turns, yielding significant insights, which I have recorded here to share with everyone.
A Careless 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, $ab$ should be the dominant term. Intuitively, $ab$ should be as close to $N$ as possible, and $a, b$ should be as close to each other as possible. Based on this, I hastily proposed a solution: "Choose between $a=b=\lfloor\sqrt{N}\rfloor$ and $a=\lfloor\sqrt{N}\rfloor, b=\lfloor\sqrt{N}\rfloor+1$." However, a group member quickly pointed out a counterexample: when $N=130$, the minimum value of $S$ is achieved at $a=10, b=13$ ($S = 130 - 130 + 10 + 13 = 23$), whereas my formula would give $a=b=11$ ($S = 130 - 121 + 11 + 11 = 31$), which is clearly not optimal.
Upon reflection, I realized I had underestimated this problem, so I set out to derive it carefully.
Direct Analysis
Without loss of generality, let $a \leq b$. First, $S$ can be transformed as follows:
\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 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: 1. In the ideal case where $\left\{\frac{N}{a}\right\}=0$, the minimum value of $a + \frac{N}{a}$ is reached at $a=\sqrt{N}$. 2. In the least ideal case, $\left\{\frac{N}{a}\right\}$ 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]$, set $b=\left\lfloor N/a\right\rfloor$, and find the minimum $S$. Obviously, this is an algorithm with complexity $\mathcal{O}(\sqrt{N})$, similar in complexity to large integer factorization. When I first derived this, I was quite surprised that such an unassuming problem would have the same complexity as large number factorization.
New Parameterization
Later, I shared the problem in a math group, and after some guidance from experts there, I realized 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 to introduce a new parameterization and refine the inequality bounds to narrow the search range. Assuming $a, b$ have the same parity, we can set $a=x-y$ and $b=x+y$, where $x, y \in \mathbb{N}$. We then get
\begin{equation}N + y^2 = x^2 + c,\quad S = 2x + c \end{equation}
The key to this new parameterization is that it changes the product $ab$ into the difference $x^2-y^2$, allowing us to see the direction of change more clearly and permitting finer bounding. If $a, b$ have different parity, we simply replace $x$ with $x+\frac{1}{2}$ and $y$ with $y+\frac{1}{2}$. The derivation is similar; we discuss both below.
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 clearly $y$ should be minimized to minimize $S$. Next, we discuss two cases. In the first case, $x^2 \leq N$, then the minimum value of $y^2 \geq x^2 - N$ is clearly $y=0$. In this case, $S=N+1-(x-1)^2$, and as $x$ increases, $S$ decreases. Since $x^2 \leq N$, the maximum possible $x$ is $x=\left\lfloor \sqrt{N}\right\rfloor$.
In the second case, $x^2 \geq N$, the minimum value of $y^2 \geq x^2 - N$ is $y=\left\lceil \sqrt{x^2 - N}\right\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$, so to minimize it, $x$ should be as small as possible. Combined with $x^2 \geq N$, we take $x=\left\lceil \sqrt{N}\right\rceil$. Note that this is calculated based on an upper bound of $S$; the actual minimum of $S$ might not be at $x=\left\lceil \sqrt{N}\right\rceil$, but we can use this result to narrow the search range. Substituting into the inequality above, we further obtain
\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 the minimum of $S$ occurs at $x=x^*, c=c^*$. Then we have
\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 the integers in the interval $\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})$ rather than $\mathcal{O}(\sqrt{N})$!
Different Parity
Assuming $a, b$ have different parity, we can set $a=\left(x+\frac{1}{2}\right)-\left(y+\frac{1}{2}\right)$ and $b=\left(x+\frac{1}{2}\right)+\left(y+\frac{1}{2}\right)$, where $x, y \in \mathbb{N}$. We then get
\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}
Similarly, we discuss two cases. First, when $\left(x+\frac{1}{2}\right)^2 \leq N$, a result similar to the previous section is $y=0$ and $x=\left\lfloor \sqrt{N}-\frac{1}{2}\right\rfloor$. Second, when $\left(x+\frac{1}{2}\right)^2 \geq N$, the minimum value of $y$ is $y=\left\lceil \sqrt{\left(x+\frac{1}{2}\right)^2 - N}-\frac{1}{2}\right\rceil$. By reasoning identical to $\eqref{eq:S1}$ and $\eqref{eq:S2}$ and substituting $x=\left\lceil \sqrt{N}-\frac{1}{2}\right\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\left(x^*+\frac{1}{2}\right) + 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
Compiling the results from the two sections above, the process for finding the minimum of $S$ can be organized as follows:
- If $N$ is a perfect square, return $x=\sqrt{N}, y=0$ (so $a=b=\sqrt{N}, c=0$);
- Otherwise, calculate $S$ for both ($x=\lfloor \sqrt{N}\rfloor, y=0$) and ($x=\lfloor \sqrt{N}-\frac{1}{2}\rfloor+\frac{1}{2}, y=\frac{1}{2}$), and record the one that gives the smaller $S$;
- Iterate through all integers $m$ in the interval $\big(\sqrt{N}-1/2, \sqrt{N} + \frac{3}{2} + \sqrt{1+ 2\sqrt{N}}\big]$. Let $x=m$ and $y=\lceil \sqrt{m^2 - N}\rceil$, as well as $x=m+\frac{1}{2}$ and $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, an expert noted that discussing the parity of $a, b$ separately was somewhat cumbersome and proposed a different 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 analysis then follows the same logic. Since $c \geq 0$, $q^2 \geq p^2 - 4N$. For a fixed $p$, minimizing $S$ is equivalent to minimizing $c$, which is equivalent to minimizing $q$. If $p^2 \leq 4N$, the minimum $q$ is 0 or 1, determined by the parity of $p$. Then from
\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$. Combined with $p^2 \leq 4N$, we have $p=\left\lfloor 2\sqrt{N}\right\rfloor$.
If $p^2 \geq 4N$, the minimum $q$ is $q=\left\lceil \sqrt{p^2 - 4N} \right\rceil + \varepsilon$, where $\varepsilon \in \{0, 1\}$ is determined by parity. Expanding this:
\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}
By substituting $p=\left\lceil 2\sqrt{N}\right\rceil$, we can derive an upper bound for the minimum $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 also serves as an upper bound for $p$.
In summary, the new process for minimizing $S$ is as follows:
- If $N$ is a perfect square, return $p=2\sqrt{N}, q=0$ (so $a=b=\sqrt{N}, c=0$);
- Otherwise, set $p = \left\lfloor 2\sqrt{N}\right\rfloor$. If $p$ is even, then $q=0$; otherwise $q=1$. Calculate $S$.
- Iterate $p$ through all integers in the interval $\big(2\sqrt{N}, 2\sqrt{N} + 2 + \sqrt{1 + 4\sqrt{N}}\big]$. For each, set $q=\left\lceil \sqrt{p^2 - 4N} \right\rceil + \varepsilon$, where $\varepsilon \in \{0, 1\}$ ensures $p, q$ have the same parity. If the resulting $S$ is smaller, update the record.
- Return $a=\frac{p-q}{2}, b=\frac{p+q}{2}, c=N-ab$.
Conclusion
This article shared the thinking and learning process for an algorithm problem that I "initially thought was a Bronze but turned out to be a King."
Address for reprinting: https://kexue.fm/archives/9775