加法链

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

## 范例

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

$$2 = 1 + 1$$

$$3 = 2 + 1$$

$$6 = 3 + 3$$

$$12 = 6 + 6$$

$$24 = 12 + 12$$

$$30 = 24 + 6$$

$$31 = 30 + 1$$

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

$$n^2 = n \cdot n$$

$$n^3 = n^2 \cdot n$$

$$n^6 = n^3 \cdot n^3$$

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

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

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

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

## 对于加法链常见的误区

计算最短的加法链并非一件易事，但我们依旧可以将这个问题分成两部分：

- 给定多个整数 $n_1, n_2, ..., n_m$，接着找到一组由 $1$ 开始并包含所有目标数字 $n_1, n_2, ..., n_m$ 的最短加法链问题

- 给定一目标数字 $n$ 且找到从 1 到目标数字 $n$ 的最短加法链问题

其中部分一给予多个整数求最短加法链的问题已经被证明为是 NP完备；而部分二给予单一目标数字 $n$ 且求最短加法链至今依旧未被任何论文严谨证明或是被普遍接受的文章指出其是 NP完备的。

许多消息来源会写下类似“给予单一目标数字 $n$ 并且找到最短加法链是 NP完备的......”等等语句，但它们多半在引用时混淆了两件事：一、Computing sequences with addition chains(1981)仅证明了在给予多个目标数字下（也就是上述的部分一）是 NP完备的；二、有些后续的引用误把 Computing sequences with addition chains(1981)的结论类推到“找到单一目标数字 $n$ 的最短加法链”上，却又未给出严格证明。

针对上述第一点的论述，Achim Flammenkamp 曾经在其网页“Shortest Addition Chains”中，明确指出：

```
Computing ℓ(n) for given n is NP-hard.
```

Downey, Leony and Sethi didn't prove anything about this statement in their 1981 SIAM article. They proved a similar one, if a set of numbers is given! Many people (and even experts) overlooked this important difference! In 2002 E. Lehmann noted in his Ph.D. thesis, p 35: "Nevertheless, an exact solution to the addition chain problem remains strangely elusive. The M-ary method runs in time polylog(n) and gives a 1 + o(1) approximation. However, even if exponentially more time is allowed, poly(n), no exact algorithm is known."

## 计算加法链的方法

目前已知的算法仅能在某些场合下以合理的时间或较小的内存使用量针对给定目标数字 $n$ 计算相对较短的链，但计算出来链并不一定是最短的加法链。

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

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

Step2. 初始化加法链，其 $x_0 = 0$ 且 $i = 1$

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

Step4. $i + 1$

Step5. 将 $x_0$ 从结果中去除

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

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

初始化 $x_0 = 0$

开始从左而右读取位数

$$1 \to x_1 = (x_0 \times 2) + 1 = (0 \times 2) + 1 = 1$$

$$1 \to x_2 = (x_1 \times 2) + 1 = (1 \times 2) + 1 = 3$$

$$0 \to x_3 = x_2 \times 2 = 3 \times 2 = 6$$

$$1 \to x_4 = (x_3 \times 2) + 1 = (6 \times 2) + 1 = 13$$

$$0 \to x_5 = x_4 \times 2 = 13 \times 2 = 26$$

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

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

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

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

## 加法链的长度

令 $l(n)$ 为目标数字 $n$ 的最小长度 $s$，则：

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

其中 $\nu(n)$ 是将 $n$ 表示成二进制后的汉明权重。

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

## Brauer 链

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

Brauer 证明了 :

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

其中 $l^*$ 表示目标数字 $n$ 加法炼的最短长度。

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

## Scholz 猜想

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

$$l(2^n-1) \le n - 1 + l(n)$$

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

## 查看更多

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

## 外部链接

- . Note that the initial "1" is not counted (so element #1 in the sequence is 0).
- F. Bergeron, J. Berstel. S. Brlek "Efficient computation of addition chains"