自然数集中 N = ab + c 时 a + b + c 的最小值
By 苏剑林 | 2023-09-20 | 37427位读者 |前天晚上微信群里有群友提出了一个问题:
对于一个任意整数$N > 100$,求一个近似算法,使得$N=a\times b+c$(其中$a,b,c$都是非负整数),并且令$a+b+c$尽量地小。
初看这道题,笔者第一感觉就是“这还需要算法?”,因为看上去自由度太大了,应该能求出个解析解才对,于是简单分析了一下之后就给出了个“答案”,结果很快就有群友给出了反例。这时,笔者才意识到这题并非那么平凡,随后正式推导了一番,总算得到了一个可行的算法。正当笔者以为这个问题已经结束时,另一个数学群的群友精妙地构造了新的参数化,证明了算法的复杂度还可以进一步下降!
整个过程波澜起伏,让笔者获益匪浅,遂将过程记录在此,与大家分享。
随手的错 #
抛开$N > 100$这个约束,将原问题可以等价变换为:
已知$a,b\in\mathbb{N},ab \leq N$,求$S = N - ab + a + b$的最小值。
很明显当$N$足够大时,$ab$应该占主项,所以直觉上就是$ab$尽量接近$N$和$a,b$尽可能向相等,于是就随手拍了个“$a=b=\left\lfloor\sqrt{N}\right\rfloor$和$a=\left\lfloor\sqrt{N}\right\rfloor,b=\left\lfloor\sqrt{N}\right\rfloor+1$”二选一的答案。然而很快就有群友给出了反例:当$N=130$时,$S$最小值在$a=10,b=13$取到,而根据笔者给出的公式则是$a=b=11$,显然不够优。
细想之下,才发现是笔者低视这个问题了,于是乎认真推导了一番~
直接分析 #
不失一般性,设$a\leq b$。首先,S可以等价变换为
\begin{equation}S = N - (\sqrt{ab}-1)^2 + (\sqrt{a}-\sqrt{b})^2\end{equation}
可以看出,$S$取最小值大致上是两个方向:1、$ab$尽量大(接近$N$);2、$a,b$尽量接近。为此,暂且设
\begin{equation}b = \left\lfloor\frac{N}{a}\right\rfloor = \frac{N}{a} - \left\{\frac{N}{a}\right\}\end{equation}
那么
\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}
考虑两个极端:
1、最理想情况下$\left\{\frac{N}{a}\right\}=0$,那么$a + \frac{N}{a}$最小值在$a=\sqrt{N}$取到。
2、最不理想的情况下,$\left\{\frac{N}{a}\right\}$可以无限接近于1,即
\begin{equation}S \to a - 1 + a + \frac{N}{a} = 2a + \frac{N}{a} - 1\end{equation}
此时最小值在$a=\sqrt{N/2}$取到。
基于以上两点,我们就可以提出一个算法:
$a$遍历$\big(\sqrt{N/2},\sqrt{N}\big]$的所有整数,令$b=\left\lfloor N/a\right\rfloor$,取$S$最小者。
很明显,这是一个复杂度为$\mathcal{O}(\sqrt{N})$的算法,跟大数分解同复杂度,所以刚推导出来那会笔者对此很震惊,这个看上去不起眼的题目居然跟大数分解是同一复杂度。
新参数化 #
后来笔者将题目分享到一个数学群,经群里的大牛指点后,才发现发现自己前面的分析还是太肤浅了,原来算法的复杂度还可以明显降低。
降低复杂度的关键是引入新的参数化,并精细地放缩不等式来缩小搜索范围。假设$a,b$是同奇偶的,那么我们可以设$a=x-y,b=x+y$,其中$x,y\in\mathbb{N}$,然后得到
\begin{equation}N + y^2 = x^2 + c,\quad S = 2x + c \end{equation}
新参数化的关键是将原本相乘的$ab$变为了相减的$x^2-y^2$,从而可以更清楚地看到变化方向,并且允许更精细的放缩。如果$a,b$是一奇一偶,那么只需要将$x$换成$x+\frac{1}{2}$、$y$换成$y+\frac{1}{2}$,推导是相似的,下面我们分别讨论。
同奇偶性 #
进一步地,我们有
\begin{equation}S = 2x + c = 2x + (N + y^2 - x^2)= N + y^2 + 1 - (x - 1)^2\end{equation}
以及$N + y^2 \geq x^2$。如果$x$已经给定,那么自然是$y$越小$S$也越小。接下来又要分两种情况讨论。
第一种情况是$x^2 \leq N$,那么$y^2 \geq x^2 - N$最小值显然是$y=0$,此时$S=N+1-(x-1)^2$,很明显$x$越大$S$就越小,再结合$x^2 \leq N$,那么最大就只能是$x=\left\lfloor \sqrt{N}\right\rfloor$了。
第二种情况是$x^2 \geq N$,那么$y^2 \geq x^2 - N$的最小值就是$y=\left\lceil \sqrt{x^2 - N}\right\rceil$,此时
\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}
最后的式子是关于$x$单调递增的,所以为了让它尽可能小,那么$x$应该尽可能小,结合$x^2 \geq N$,那么$x=\left\lceil \sqrt{N}\right\rceil$。注意这是基于$S$的上界算出来的,实际$S$的最小值未必就在$x=\left\lceil \sqrt{N}\right\rceil$取到,但我们可以利用这个结果来缩小搜索范围。代入上述不等式后,进一步得到
\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}
这提供了$S$的最小值的一个上界。假设$S$取最小值时$x=x^*,c=c^*$,那么有
\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}
这就意味着我们只需要搜索$\big[\sqrt{N},\sqrt{N} + \frac{3}{2} + \sqrt{1+ 2\sqrt{N}}\big]$的整数就可以找到最优解,复杂度是$\mathcal{O}(\sqrt[4]{N})$而不是$\mathcal{O}(\sqrt{N})$!
一奇一偶 #
假设$a,b$是一奇一偶,那么我们可以设$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)$,其中$x,y\in\mathbb{N}$,然后得到
\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}
同样要分两种情况讨论。第一,当$\left(x+\frac{1}{2}\right)^2\leq N$时,类似上一节的结果是$y=0,x=\left\lfloor \sqrt{N}-\frac{1}{2}\right\rfloor$。第二,当$\left(x+\frac{1}{2}\right)^2\geq N$时,$y$的最小值是$y=\left\lceil \sqrt{\left(x+\frac{1}{2}\right)^2 - N}-\frac{1}{2}\right\rceil$,那么跟$\eqref{eq:S1},\eqref{eq:S2}$同理,代入$x=\left\lceil \sqrt{N}-\frac{1}{2}\right\rceil$,有
\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}
因此有
\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}
汇总结果 #
综合以上两节的结果,我们可以将求$S$的最小值流程整理如下:
1、如果$N$是平方数,那么返回$x=\sqrt{N},y=0$($a=b=\sqrt{N},c=0$);
2、否则,记录$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}$中让$S$较小者;
3、遍历$\big(\sqrt{N}-1/2,\sqrt{N} + \frac{3}{2} + \sqrt{1+ 2\sqrt{N}}\big]$的所有整数$m$,令$x=m,y=\left\lceil \sqrt{m^2 - N}\right\rceil$以及$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}$,如果它们对应的$S$更小,那么覆盖记录的$x,y$;
4、返回$a=x-y,b=x+y,c=N-ab$。
又一思路 #
文章发出后,有一位大牛觉得以上分是否同奇偶的讨论过于麻烦,于是又提出了一个新的参数化方式:令$p=a+b,q=b-a$,那么
\begin{equation}4N - p^2 + q^2 = 4c, \quad S = p + c \end{equation}
注意这里$p,q$必须是同奇偶的,才能保证$c$是一个整数。
接下来的分析跟前面就几乎一样了,因为$c\geq 0$,所以$q^2\geq p^2 - 4N$。考虑给定$p$,那么$S$的最小值等价于$c$的最小值,也等价于$q$的最小值。如果$p^2 \leq 4N$,那么$q$的最小值是$0$或$1$,这需要根据$p,q$同奇偶来确定。然后根据
\begin{equation}4S = 4p+4c = 4p + 4N - p^2 + q^2 = 4N + q^2 + 4 - (p - 2)^2 \end{equation}
所以$S$最小对应$p$最大,结合$p^2 \leq 4N$则有$p=\left\lfloor 2\sqrt{N}\right\rfloor$。
如果$p^2 \geq 4N$,那么$q$的最小值是$q=\left\lceil \sqrt{p^2 - 4N} \right\rceil + \varepsilon$,这里$\varepsilon\in\{0,1\}$同样要根据$p,q$同奇偶来确定。然后我们代入
\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}
代入$p=\left\lceil 2\sqrt{N}\right\rceil$,我们可以得出$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}
因为$S = p + c \geq p$,所以这也是$p$的一个上界。
综上所述,新的求$S$的最小值流程整理如下:
1、如果$N$是平方数,那么返回$p=2\sqrt{N},q=0$($a=b=\sqrt{N},c=0$);
2、否则,令$p = \left\lfloor 2\sqrt{N}\right\rfloor$,如果$p$是偶数,则$q=0$,否则$q=1$,计算此时的$S$;
3、遍历$\big(2\sqrt{N},2\sqrt{N} + 2 + \sqrt{1 + 4\sqrt{N}}\big]$的所有整数为$p$,令$q=\left\lceil \sqrt{p^2 - 4N} \right\rceil + \varepsilon$,$\varepsilon\in\{0,1\}$来保证$p,q$同奇偶,如果它们对应的$S$更小,那么覆盖记录的$p,q$;
4、返回$a=\frac{p-q}{2},b=\frac{p+q}{2},c=N-ab$。
文章小结 #
本文分享了一道“以为是个青铜,结果是个王者”的算法题的思考和学习过程。
转载到请包括本文地址:https://kexue.fm/archives/9775
更详细的转载事宜请参考:《科学空间FAQ》
如果您还有什么疑惑或建议,欢迎在下方评论区继续讨论。
如果您觉得本文还不错,欢迎分享/打赏本文。打赏并非要从中获得收益,而是希望知道科学空间获得了多少读者的真心关注。当然,如果你无视它,也不会影响你的阅读。再次表示欢迎和感谢!
如果您需要引用本文,请参考:
苏剑林. (Sep. 20, 2023). 《自然数集中 N = ab + c 时 a + b + c 的最小值 》[Blog post]. Retrieved from https://kexue.fm/archives/9775
@online{kexuefm-9775,
title={自然数集中 N = ab + c 时 a + b + c 的最小值},
author={苏剑林},
year={2023},
month={Sep},
url={\url{https://kexue.fm/archives/9775}},
}
September 20th, 2023
[...]Read More [...]
September 20th, 2023
在下,即文中所说提出这个问题的水友。感谢苏老师解答的同时,补充一下这个问题的实际背景。是的,这个问题来自于,实际项目中的真实问题的数学概括。这个问题是这样的:
我在应用pytorch,处理一个状态转移矩阵的长序列时遇到了并行计算的困难,比如:输入矩阵序列S=[A1,A2,A3……A(i)],我想要输出得到[A1,A1*A2,A1*A2*A3,……,A1*A2*A3*……A(i-1)*A(i)],似乎没有现成的程序可以并行的处理这个问题。在考虑到矩阵乘法符合结合律后,我觉得可以有并行的操作空间。利用某种方法,可以在最慢2*log2(N)的时间复杂内完成这个问题,但这种方法的缺点是操作有一些复杂,空间复杂度高,以我目前的代码水平很可能无法完成。因此,退而求其次,我想出了len(S)=N=a×b+c,的拆分方法,先操作a×b的方阵并行的计算出序贯乘积,结尾再把尾部的c个矩阵串行加入。故,总体时间复杂度为a+b+c,也就是这个问题的由来。在具体实践时,一开始我和苏老师一样,都直接尝试了a=int(N^0.5),结果发现在某些N时速度会变得非常慢,实际过程与上文所阐述相似,不再赘述。
经过以上方法的改进,我的程序得到30%左右速度的提升。本程序的实践过程可以在我的github找到(下附),目前它不仅仅可以处理矩阵乘法,并且可以拓展到一切符合结合律的序列的并行计算,兼容cpu/cuda、16/32f,并可以实现对矩阵行列归一化特性的保持,欢迎浏览使用,以及共同完善,谢谢!
(github.com/Changkai9888/Pytorch_tool/blob/main/associative_law_operation_accelerator_for_pyorch.py)
非常有趣且具有现实意义的问题,如果不介意空间复杂度稍微高点的话,能否直接换成这样一个问题,已知a,b,N都是正整数,a*b大于等于N,求a+b的最小值,这样也许可以直接令a=[N^0.5]或a=[N^0.5]+1
不好意思,之前说错,直接令a=int(N^0.5),如果N不等于a^2或a*(a+1),就随便补充数据至a*(a+1)或a*(a+2),最后得到结果也只取前N项,不知道是否会快一些
送你一只可爱的奶龙,并告诉你只有N是已知数。
这里的乘法,泛指任意满足结合律的运算吧。感觉associative scan其实不难实现呀~参考 https://kexue.fm/archives/9554
这个算法本身的分析难度比您所提出问题的难度大不少,原本只需要 associative scan 即可
September 20th, 2023
厉害~,这是怎么想到的……
September 21st, 2023
其实这题目不算是用近似算法求解的。
近似快,绝对准。其实这正是我所需要的。
他初衷可能确实只是想找到一个快速高效的近似算法,而本文的目的是探索精确求解的复杂度。
October 21st, 2023
苏神微信群怎么加
pc浏览器访问首页,然后看右上角
October 1st, 2024
真令人惊叹,每次见到一些奇思妙想都要忍住拍手称快!令人惊叹的灵感来自于哪里?为什么我想不到?他们进行了哪些特定的学习训练、探索与思考才能想到,我所认为的灵感,实际上是不是别人习以为常的显然,明显,是否可以复制他人的