The Minimum of a + b + c under N = ab + c in the Natural Numbers

自然数集中 N = ab + c 时 a + b + c 的最小值 苏剑林 · 2023-09-20 · Questions optimal problem

The other night, someone in a WeChat group posed the following question:

For an arbitrary integer $N > 100$, find an approximation algorithm such that $N=a\times b+c$ (where $a,b,c$ are all non-negative integers), and make $a+b+c$ as small as possible.

At first glance, my reaction was "does this really need an algorithm?" — it looked like there was so much freedom in the parameters that a closed-form solution should exist. So after a bit of quick analysis I gave an "answer," and almost immediately someone in the group produced a counterexample. That's when I realized the problem wasn't as trivial as it looked, and I went ahead and worked through it properly, eventually arriving at a workable algorithm. Just as I thought the matter was settled, someone in another math group came up with an elegant new parametrization, showing that the complexity of the algorithm could be reduced even further!

The whole process had quite a few twists and turns, and I learned a lot from it, so I'm recording it here to share with everyone. more

A Careless Mistake

Setting aside the constraint $N > 100$ for a moment, the original problem can be equivalently rephrased as:

Given $a,b\in\mathbb{N},ab \leq N$, find the minimum of $S = N - ab + a + b$.

It's clear that when $N$ is large enough, $ab$ should dominate, so intuitively the idea is to make $ab$ as close as possible to $N$, and $a,b$ as close to each other as possible. So I casually threw out an answer choosing between "$a=b=\left\lfloor\sqrt{N}\right\rfloor$ or $a=\left\lfloor\sqrt{N}\right\rfloor,b=\left\lfloor\sqrt{N}\right\rfloor+1$." But very quickly someone gave a counterexample: when $N=130$, the minimum of $S$ is attained at $a=10,b=13$, whereas the formula I gave produces $a=b=11$, which is clearly not optimal.

On closer thought, I realized I had underestimated this problem, so I sat down and worked through it carefully.

Direct Analysis

Without loss of generality, let $a\leq b$. First, S can be equivalently rewritten as

\begin{equation}S = N - (\sqrt{ab}-1)^2 + (\sqrt{a}-\sqrt{b})^2\end{equation}

We can see that minimizing $S$ roughly involves two directions: 1) making $ab$ as large as possible (close to $N$); 2) making $a,b$ as close as possible to each other. 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}

so that

\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 extreme cases:

1. In the most ideal case, $\left\{\frac{N}{a}\right\}=0$, so the minimum of $a + \frac{N}{a}$ is attained at $a=\sqrt{N}$.
2. In the least ideal case, $\left\{\frac{N}{a}\right\}$ can get arbitrarily close to 1, i.e.,
\begin{equation}S \to a - 1 + a + \frac{N}{a} = 2a + \frac{N}{a} - 1\end{equation}
in which case the minimum is attained at $a=\sqrt{N/2}$.

Based on these two points, we can propose an algorithm:

Let $a$ range over all integers in $\big(\sqrt{N/2},\sqrt{N}\big]$, set $b=\left\lfloor N/a\right\rfloor$, and take the one giving the smallest $S$.

Clearly this is an algorithm of complexity $\mathcal{O}(\sqrt{N})$, the same complexity as integer factorization — which, upon first deriving it, struck me as quite surprising: this seemingly innocuous problem turns out to have the same complexity as factoring large numbers.

A New Parametrization

Later, I shared the problem with a math group, and after being pointed in the right direction by some of the experts there, I realized that my earlier analysis had still been too shallow — the complexity of the algorithm can be lowered significantly further.

The key to reducing the complexity is to introduce a new parametrization and to carefully bound the inequalities in order to narrow the search range. Suppose $a,b$ have the same parity; then we can set $a=x-y,b=x+y$, where $x,y\in\mathbb{N}$, giving

\begin{equation}N + y^2 = x^2 + c,\quad S = 2x + c \end{equation}

The key feature of this new parametrization is that it turns the originally multiplicative term $ab$ into the subtractive term $x^2-y^2$, making it much easier to see the direction of change and allowing for finer bounding. If $a,b$ have different parities, we only need to replace $x$ with $x+\frac{1}{2}$ and $y$ with $y+\frac{1}{2}$; the derivation is similar. Below we discuss the two cases 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}

as well as $N + y^2 \geq x^2$. If $x$ is fixed, then naturally the smaller $y$ is, the smaller $S$ becomes. Next we again need to distinguish two cases.

The first case is $x^2 \leq N$, in which the minimum of $y^2 \geq x^2 - N$ is clearly $y=0$, giving $S=N+1-(x-1)^2$; it's clear that the larger $x$ is, the smaller $S$ becomes, and combined with $x^2 \leq N$ the maximum value it can take is $x=\left\lfloor \sqrt{N}\right\rfloor$.

The second case is $x^2 \geq N$, in which the minimum of $y^2 \geq x^2 - N$ is $y=\left\lceil \sqrt{x^2 - N}\right\rceil$, giving

\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 in $x$, so to make it as small as possible, $x$ should be as small as possible; combined with $x^2 \geq N$, we get $x=\left\lceil \sqrt{N}\right\rceil$. Note that this is derived from an upper bound on $S$, so the actual minimum of $S$ need not be attained at $x=\left\lceil \sqrt{N}\right\rceil$, but we can use this result to narrow the search range. Substituting into the above inequality, 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 gives an upper bound on the minimum of $S$. Suppose the minimum of $S$ is attained 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 over integer values of $\big[\sqrt{N},\sqrt{N} + \frac{3}{2} + \sqrt{1+ 2\sqrt{N}}\big]$ to find the optimal solution — complexity $\mathcal{O}(\sqrt[4]{N})$ rather than $\mathcal{O}(\sqrt{N})$!

Different Parity

Suppose $a,b$ have different parities; then we can set $a=\left(x+\frac{1}{2}\right)-\left(y+\frac{1}{2}\right),b=\left(x+\frac{1}{2}\right)+\left(y+\frac{1}{2}\right)$, where $x,y\in\mathbb{N}$, giving

\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 distinguish two cases. First, when $\left(x+\frac{1}{2}\right)^2\leq N$, similar to the previous section the result is $y=0,x=\left\lfloor \sqrt{N}-\frac{1}{2}\right\rfloor$. Second, when $\left(x+\frac{1}{2}\right)^2\geq N$, the minimum of $y$ is $y=\left\lceil \sqrt{\left(x+\frac{1}{2}\right)^2 - N}-\frac{1}{2}\right\rceil$; then, analogously to $\eqref{eq:S1},\eqref{eq:S2}$, substituting $x=\left\lceil \sqrt{N}-\frac{1}{2}\right\rceil$ gives

\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}

and 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

Combining the results of the above two sections, the procedure for finding the minimum of $S$ can be summarized as follows:

1. If $N$ is a perfect square, return $x=\sqrt{N},y=0$ ($a=b=\sqrt{N},c=0$);
2. Otherwise, record whichever of $x=\left\lfloor \sqrt{N}\right\rfloor,y=0$, $x=\left\lfloor \sqrt{N}-\frac{1}{2}\right\rfloor+\frac{1}{2},y=\frac{1}{2}$ gives the smaller $S$;
3. Loop over all integers $m$ in $\big(\sqrt{N}-1/2,\sqrt{N} + \frac{3}{2} + \sqrt{1+ 2\sqrt{N}}\big]$, set $x=m,y=\left\lceil \sqrt{m^2 - N}\right\rceil$ and $x=m+\frac{1}{2},y=\left\lceil \sqrt{\left(m+\frac{1}{2}\right)^2 - N}-\frac{1}{2}\right\rceil + \frac{1}{2}$, and if the corresponding $S$ is smaller, overwrite the recorded $x,y$;
4. Return $a=x-y,b=x+y,c=N-ab$.

Yet Another Approach

After the article was posted, one of the experts felt that splitting the discussion by same/different parity was overly cumbersome, and proposed yet another parametrization: let $p=a+b,q=b-a$, so that

\begin{equation}4N - p^2 + q^2 = 4c, \quad S = p + c \end{equation}

Note that here $p,q$ must have the same parity in order to guarantee that $c$ is an integer.

The subsequent analysis is almost identical to before, since $c\geq 0$, and so $q^2\geq p^2 - 4N$. Given $p$, minimizing $S$ is equivalent to minimizing $c$, which is in turn equivalent to minimizing $q$. If $p^2 \leq 4N$, then the minimum of $q$ is $0$ or $1$, depending on the parity of $p,q$. Then, from

\begin{equation}4S = 4p+4c = 4p + 4N - p^2 + q^2 = 4N + q^2 + 4 - (p - 2)^2 \end{equation}

the minimum of $S$ corresponds to the maximum of $p$, and combined with $p^2 \leq 4N$ we get $p=\left\lfloor 2\sqrt{N}\right\rfloor$.

If $p^2 \geq 4N$, then the minimum of $q$ is $q=\left\lceil \sqrt{p^2 - 4N} \right\rceil + \varepsilon$, where $\varepsilon\in\{0,1\}$ likewise must be determined by the parity of $p,q$. Substituting into

\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}

and plugging in $p=\left\lceil 2\sqrt{N}\right\rceil$, we can derive an upper bound on the minimum 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$.

To sum up, the new procedure for finding the minimum of $S$ is as follows:

1. If $N$ is a perfect square, return $p=2\sqrt{N},q=0$ ($a=b=\sqrt{N},c=0$);
2. Otherwise, let $p = \left\lfloor 2\sqrt{N}\right\rfloor$; if $p$ is even, set $q=0$, else set $q=1$, and compute the corresponding $S$;
3. Loop over all integers $p$ in $\big(2\sqrt{N},2\sqrt{N} + 2 + \sqrt{1 + 4\sqrt{N}}\big]$, set $q=\left\lceil \sqrt{p^2 - 4N} \right\rceil + \varepsilon$, with $\varepsilon\in\{0,1\}$ chosen so that $p,q$ have matching parity; if the corresponding $S$ is smaller, overwrite the recorded $p,q$;
4. Return $a=\frac{p-q}{2},b=\frac{p+q}{2},c=N-ab$.

Summary

This post shares the process of thinking through and learning from a problem that "looked like a bronze-tier puzzle but turned out to be a grandmaster."