加法鏈

在數學中，加法鏈（英文：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$

計算加法鏈的方法

計算最小長度的加法鏈並非一件易事，我們可以將這個問題拓撲成：找到一組由一系列自然數所組成的序數，但很不幸地，這個問題是 NP完備。目前已知的算法僅能在某些場合下以合理的時間或較小的記憶體使用量針對給定目標數字 $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$……（OEIS數列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)\neq l^{*}(n)$，例如 $n=2^{6106}+2^{3048}+2^{2032}+2^{2016}+1$，其中 $l^{*}(n)=6110,l(n)\leq 6109$。$n$ 的最小值是 $12509$。

Scholz 猜想

主条目：Scholz conjecture

Scholz 猜想（也被稱為 Scholz–Brauer 或 Brauer–Scholz 猜想），以 Arnold Scholz 和 Alfred T. Brauer 的名子命名，是一個來自 1937 年的猜想，其猜想如下：

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

這個不等式對所有已知的 Hansen 數成立，Hansen 數是 Brauer 數的一種廣義定義；Neill Clift 曾使用計算機檢查了所有 $n\leq 5784688$ 的 Hansen數（$5784689$ 不是 Hansen 數）。Neill Clift 也進一步驗證了當 $n\leq 64$ 時，$l(2^{n}-1)=n-1+l(n)$。

查看更多

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

外部連結

• Template:OEIS el. 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"