連鎖反応

数学において、正の整数nを計算するための加算連鎖は、 1 からnまで続く自然数の数列で表され、その数列の各数は前の 2 つの数の和になります。加算連鎖の長さは、その数列のすべての数を表すのに必要な和の数であり、数列の濃度より 1 少ない数です。 ^{[ 1 ]}

例として、(1,2,3,6,12,24,30,31) は長さ 7 の 31 の加算チェーンです。

2 = 1 + 1

3 = 2 + 1

6 = 3 + 3

12 = 6 + 6

24 = 12 + 12

30 = 24 + 6

31 = 30 + 1

加算連鎖は、加算連鎖べき乗に利用できます。この方法では、整数指数を用いたべき乗を、指数に対する加算連鎖の長さに等しい回数の乗算で実行できます。例えば、31に対する加算連鎖を用いると、任意の数nの31乗を計算する際に、繰り返し乗算で必要な30回の乗算と、二乗によるべき乗で必要な8回の乗算の代わりに、わずか7回の乗算で済む方法が得られます。

n ² = n × n

n ³ = n ² × n

n ⁶ = n ³ × n ³

n ¹² = n ⁶ × n ⁶

n ²⁴ = n ¹² × n ¹²

n ³⁰ = n ²⁴ × n ⁶

n ³¹ = n ³⁰ × n

最小長の加算チェーンを計算することは容易ではありません。一連の値のそれぞれを同時に形成するチェーンを見つけるという問題の一般化バージョンはNP完全です。^{[ 2 ]}妥当な時間や少ないメモリ使用量を保証して、与えられた数に対して最小の加算チェーンを計算できる既知のアルゴリズムはありません。ただし、必ずしも最適ではない比較的短いチェーンを計算するいくつかの手法が知られています。^{[ 3 ]}

比較的短い加算チェーンを計算する非常によく知られた手法の 1 つは、 2 乗による指数計算に似たバイナリ法です。この方法では、数に対する加算チェーンは、${\displaystyle n}$は、加算チェーンから再帰的に得られます。${\displaystyle n'=\lfloor n/2\rfloor }$。 もし${\displaystyle n}$偶数であれば、1つの追加和で得られる。${\displaystyle n=n'+n'}$。 もし${\displaystyle n}$奇数の場合、この方法は 2 つの和を使用して計算することでそれを取得します${\displaystyle n-1=n'+n'}$そして1を加える。^{[ 3 ]}

加算連鎖を見つけるための因数分解法は、数の素因数分解に基づいています。${\displaystyle n}$代表される。${\displaystyle n}$番号があります${\displaystyle p}$その主要な要素の1つとして、次に加算チェーン${\displaystyle n}$チェーンから始めることで取得できます${\displaystyle n/p}$そして、それにチェーンを連結して${\displaystyle p}$それぞれの数値を乗算して修正する${\displaystyle n/p}$因数法と二進法の考え方は、任意の数を選択することで、ブラウアーのm進法に組み合わせることができる。${\displaystyle m}$（分割するかどうかに関わらず）${\displaystyle n}$）、再帰的にチェーンを構築して${\displaystyle \lfloor n/m\rfloor }$チェーンを連結して${\displaystyle m}$（上記と同様に修正して）${\displaystyle m\lfloor n/m\rfloor }$そして残りを加える。これらのアイデアをさらに改良すると、スライディングウィンドウ法と呼ばれる一連の手法が生まれる。^{[ 3 ]}

させて${\displaystyle l(n)}$最小値を表す${\displaystyle s}$長さの加算チェーンが存在する${\displaystyle s}$計算する${\displaystyle n}$知られているように、 $${\displaystyle \log _{2}n+\log _{2}\nu (n)-2.13\leq l(n)\leq \log _{2}n+\nu (n)-1,}$$$${\displaystyle l(n)\leq \log _{2}n+{\bigl (}1+o(1){\bigr )}{\frac {\log _{2}n}{\log _{2}\log _{2}n}},}$$ どこ${\displaystyle \nu (n)}$は、 のバイナリ展開のハミング重み（1の数）です。${\displaystyle n}$[ ^{4 ]​}

追加チェーンを取得できます${\displaystyle 2n}$加算チェーンから${\displaystyle n}$追加の1つの合計を含めることによって${\displaystyle 2n=n+n}$そこから不等式が導かれる${\displaystyle l(2n)\leq l(n)+1}$鎖の長さについて${\displaystyle n}$そして${\displaystyle 2n}$しかし、これは必ずしも平等とは限らない。${\displaystyle 2n}$この方法で得られたものよりも短い鎖を持つ可能性がある。例えば、${\displaystyle l(382)=l(191)=11}$Knuthによって観察された。^{[ 5 ]}は、${\displaystyle 2n}$鎖が短い${\displaystyle n}$、 となることによって${\displaystyle l(2n)<l(n)}$最小${\displaystyle n}$これが起こる理由は${\displaystyle n=375494703}$[ ^{6 ]に}続いて${\displaystyle 602641031}$、${\displaystyle 619418303}$など（ OEISの配列A230528）。

ブラウアー連鎖またはスター加算連鎖とは、各項の計算に使用される加算が直前の項を使用する加算連鎖のことである。ブラウアー数とは、ブラウアー連鎖が最適となる数のことである。^{[ 5 ]}

ブラウアーは、

l ^* (2 ⁿ −1) ≤ n − 1 + l ^* ( n )

どこで${\displaystyle l^{*}}$は最短の星鎖の長さです。 ^{[ 7 ]} 多くの値に対して${\displaystyle n}$、特に${\displaystyle n<12509}$、それらは等しい: ^{[ 8 ]} l ( n )  = l ^* ( n ) 。しかし、Hansen は、 l ( n ) ≠ l ^* ( n )となるnの値が存在することを示した。例えば、n = 2 ⁶¹⁰⁶ + 2 ³⁰⁴⁸ + 2 ²⁰³² + 2 ²⁰¹⁶ + 1では、l ^* ( n ) = 6110、l ( n ) ≤ 6109となる。そのような最小のnは 12509 である。                

ショルツ予想（ショルツ＝ブラウアー予想またはブラウアー＝ショルツ予想とも呼ばれる）は、アーノルド・ショルツとアルフレッド・T・ブラウアーにちなんで名付けられた1937年の予想で、

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

この不等式は、ブラウアー数の一般化であるすべてのハンセン数に対して成り立つことが知られています。ニール・クリフトは、すべてのハンセン数が成り立つことをコンピュータで確認しました。${\displaystyle n\leq 5784688}$はハンセンである（5784689はそうではない）。^{[ 6 ]} クリフトはさらに、実際には${\displaystyle l(2^{n}-1)=n-1+l(n)}$すべての人々のために${\displaystyle n\leq 64}$[ ^{5 ]​}

• 足し算と引き算の連鎖
• ベクトル加算連鎖
• ルーカスチェーン

• OEISシーケンスA003313 (n の最短加算チェーンの長さ)。最初の「1」はカウントされないことに注意してください (したがって、シーケンスの要素 #1 は 0 です)。
• F. Bergeron、J. Berstel、S. Brlek「加算連鎖の効率的な計算」