加法鏈

在數學中，加法鏈（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"