加法链

在数学中，加法链（英语：Addition chain）是由一组由自然数所组成的序列，该序列以 1 开始，到目标数字 ${\displaystyle n}$ 结束，例如：${\displaystyle (1,2,3,6,12)}$，即为目标数字为 ${\displaystyle 12}$ 的加法链且序列中的每个数为序列出现过的两数之和。而整个链所需要的加法次数则被称作加法链的长度，通常记为 ${\displaystyle s}$，而 ${\displaystyle s}$ 的值为数列内所包含的基数数量再减去一^[1]，以前面的例子来说 ${\displaystyle s=4}$。

范例

这里有个简单的例子：${\displaystyle (1,2,3,6,12,24,30,31)}$ 就是一个目标数字 ${\displaystyle n}$ 为 31 且 ${\displaystyle s=7}$ 的加法链

${\displaystyle 2=1+1}$

${\displaystyle 3=2+1}$

${\displaystyle 6=3+3}$

${\displaystyle 12=6+6}$

${\displaystyle 24=12+12}$

${\displaystyle 30=24+6}$

${\displaystyle 31=30+1}$

在加法链求幂的方法中就有使用到加法链的方法，而这个方法允许我们将目标数字 ${\displaystyle n}$ 设定为某任意数 ${\displaystyle A}$ 的指数，进而计算出该数的幂；举例来说，我们现有一数 ${\displaystyle A^{x}}$，则我们可以将加法链的目标数字 ${\displaystyle n}$ 设定为 ${\displaystyle x}$，进而计算出其对应的加法链。更具体的说，假设我们现需要计算一自然数${\displaystyle A^{31}}$ 的幂，则可以扩展成求目标数字 ${\displaystyle n}$ 为 ${\displaystyle 31}$ 的加法链的问题。就结果来说，总共就只需要计算七次乘法即可求出其幂，相较于不断的连乘 ${\displaystyle n}$ 所需的 ${\displaystyle 30}$ 次乘法以及平方求幂的 8 次乘法所需要的乘法次数要少：

${\displaystyle n^{2}=n\cdot n}$

${\displaystyle n^{3}=n^{2}\cdot n}$

${\displaystyle n^{6}=n^{3}\cdot n^{3}}$

${\displaystyle n^{12}=n^{6}\cdot n^{6}}$

${\displaystyle n^{24}=n^{12}\cdot n^{12}}$

${\displaystyle n^{30}=n^{24}\cdot n^{6}}$

${\displaystyle n^{31}=n^{30}\cdot n}$

计算加法链的方法

计算最小长度的加法链并非一件易事，我们可以将这个问题拓扑成：找到一组由一系列自然数所组成的序数，但很不幸地，这个问题是 NP完备^[2]。目前已知的算法仅能在某些场合下以合理的时间或较小的记忆体使用量针对给定目标数字 ${\displaystyle n}$ 计算相对较短的链，但计算出来链并不一定是最短的加法链^[3]。

一种广为人知的计算相对较短加法链的算法是二进制方法，类似于平方求幂。在这种方法中，目标数字 ${\displaystyle n}$ 的加法链是由以下方式计算出来的：

Step1. 先将目标数字 ${\displaystyle n}$ 转换至二进制

Step2. 初始化加法链，其 ${\displaystyle x_{0}=0}$ 且 ${\displaystyle i=1}$

Step3. 从左至右依序读取位数，若为 ${\displaystyle 0}$ 则 ${\displaystyle x_{i}=x_{i-1}\cdot 2}$，否则 ${\displaystyle x_{i}=x_{i-1}\cdot 2+1}$

Step4. ${\displaystyle i+1}$

Step5. 将 ${\displaystyle x_{0}}$ 从结果中去除

以下使用二进制方法计算目标数字为 26 的加法链范例：

先将目标数字 ${\displaystyle n}$ 以二进制表示 ${\displaystyle 26_{10}\to 11010_{2}}$

初始化 ${\displaystyle x_{0}=0}$

开始从左而右读取位数

${\displaystyle 1\to x_{1}=(x_{0}\times 2)+1=(0\times 2)+1=1}$

${\displaystyle 1\to x_{2}=(x_{1}\times 2)+1=(1\times 2)+1=3}$

${\displaystyle 0\to x_{3}=x_{2}\times 2=3\times 2=6}$

${\displaystyle 1\to x_{4}=(x_{3}\times 2)+1=(6\times 2)+1=13}$

${\displaystyle 0\to x_{5}=x_{4}\times 2=13\times 2=26}$

至此我们得到了一序列为 ${\displaystyle [0,1,3,6,13,26]}$。最后，去除 ${\displaystyle x_{0}}$ 之后，我们就可得出目标数字为 ${\displaystyle 26}$ 以二进制方法所产生的加法链为 ${\displaystyle [1,3,6,13,26]}$。

我们同样可以使用被称作因数法的方法来尝试寻找最短加法链，其底层逻辑是目标数字 ${\displaystyle n}$ 的质因数分解。如果 ${\displaystyle n}$ 有一个质因数${\displaystyle p}$，则可以先找到目标数字为 ${\displaystyle n/p}$ 的加法链，接着与一个目标数字 ${\displaystyle p}$ 的加法链串接，同时透过将序列内每个元素乘以 ${\displaystyle n/p}$ 来重构该加法链，最终得到目标数字 ${\displaystyle n}$ 的加法链。

而因数法和二进制方法可以结合成 Brauer 的 m 进位方法，其方法是透过随机选择一自然数 ${\displaystyle m}$（无论是否能整除 ${\displaystyle n}$），先计算目标数字 ${\displaystyle m}$ 的加法链，接着计算目标数字 ${\displaystyle \lfloor n/m\rfloor }$ 的加法链，最后将两加法链串接起来获得目标数字为 ${\displaystyle m\lfloor n/m\rfloor }$ 的加法链，最后加上余数来得到最终的结果。

正因为有新方法持续不断的被提出，而成就了一系列被称为滑动窗口方法的算法^[3]。

加法链的长度

令 ${\displaystyle l(n)}$ 为目标数字 ${\displaystyle n}$ 的最小长度 ${\displaystyle s}$，则： $${\displaystyle \log _{2}n+\log _{2}\nu (n)-2.13\leq l(n)\leq \log _{2}n+{\bigl (}1+o(1){\bigr )}{\frac {\log _{2}n}{\log _{2}\log _{2}n}}}$$

其中 ${\displaystyle \nu (n)}$ 是将 ${\displaystyle n}$ 表示成二进制后的汉明权重^[4]。

可以在为目标数字 ${\displaystyle n}$ 的加法链末尾加入一个新的值 ${\displaystyle 2n=n+n}$，从而将目标数字 ${\displaystyle n}$ 的加法链转换为目标数字 ${\displaystyle 2n}$ 的加法链，从而得到不等式 ${\displaystyle l(2n)\leq l(n)+1}$，然而目标数字 ${\displaystyle n}$ 和目标数字 ${\displaystyle 2n}$ 的加法链长度并非总是符合前述的不等式，在某些情况下，目标数字 ${\displaystyle 2n}$ 是有可能可以透过某些方法获得更短的加法链。如 Knuth 就观察到 ${\displaystyle l(382)=l(191)=11}$^[5]。甚至可能出现目标数字 ${\displaystyle 2n}$ 的加法链比目标数字 ${\displaystyle n}$ 的加法链更短的状况；目前已被找到符合 ${\displaystyle l(2n)<l(n)}$ 且最小的 ${\displaystyle n}$ 发生在 ${\displaystyle n=375494703}$ 时^[6]，随后是 ${\displaystyle 602641031}$、${\displaystyle 619418303}$……（OEIS数列A230528）。

Brauer 链

Brauer 链也是一种加法链。Brauer数是指对于该目标数字而言，Brauer链产生出来的加法链是最短的^[5]。

Brauer 证明了 :

${\displaystyle l^{*}(2^{n}-1)\leq n-1+l^{*}(n)}$

其中 ${\displaystyle l^{*}}$ 表示目标数字 ${\displaystyle n}$ 加法炼的最短长度^[7]。

当 ${\displaystyle 12509>n}$ 时，${\displaystyle l(n)=l^{*}(n)}$等式成立^[8]。但 Hansen 表示，有些 ${\displaystyle n}$ 的值使得 ${\displaystyle l(n)\neq l^{*}(n)}$，例如 ${\displaystyle n=2^{6106}+2^{3048}+2^{2032}+2^{2016}+1}$，其中 ${\displaystyle l^{*}(n)=6110,l(n)\leq 6109}$。${\displaystyle n}$ 的最小值是 ${\displaystyle 12509}$。

Scholz 猜想

主条目：Scholz conjecture

Scholz 猜想（也被称为 Scholz–Brauer 或 Brauer–Scholz 猜想），以 Arnold Scholz 和 Alfred T. Brauer 的名子命名，是一个来自 1937 年的猜想，其猜想如下：

${\displaystyle l(2^{n}-1)\leq n-1+l(n)}$

这个不等式对所有已知的 Hansen 数成立，Hansen 数是 Brauer 数的一种广义定义；Neill Clift 曾使用计算机检查了所有 ${\displaystyle n\leq 5784688}$ 的 Hansen数（${\displaystyle 5784689}$ 不是 Hansen 数）^[6]。Neill Clift 也进一步验证了当 ${\displaystyle n\leq 64}$ 时，${\displaystyle l(2^{n}-1)=n-1+l(n)}$^[5]。

查看更多

• Addition-subtraction chain
• Vectorial addition chain
• Lucas chain