ホイール因数分解
最初のいくつかの素数と互いに素な数を生成するアルゴリズム
n = 2 × 3 × 5 = 30のホイール因数分解。黄色の領域には素数は発生しません。

ホイール因数分解は、最初のいくつかの素数によって決まる加算を繰り返して自然数のシーケンスを生成する方法であり、生成される数は、構成上、これらの素数と 互いに素になります。

説明

選ばれた数n（通常は4または5以下）に対して、最初のn個の素数は、これらの素数と互いに素であることが事前に分かっている自然数の列を生成するための具体的な方法を決定します。つまり、これらの素数はすべて、これらの素数のいずれの倍数にもならないことが分かっています。したがって、この方法は整数因数分解における試し割り法の改良に使用できます。なぜなら、生成された数は、これらの小さな素数による試し割りでテストする必要がないからです。

試し割り法は、因数分解する数を整数（2、3、4、5、…）の昇順で順に割っていく方法です。一般的な改良法としては、素数のみ、つまり2、3、5、7、11、…で割る方法があります。ホイール分解法では、基底と呼ばれる小さな数のリスト（通常は最初の数個の素数）から開始し、基底に含まれるすべての数と 互いに素である整数のリスト（ホイール）を生成します。

すると、「ホイールを転がす」ことで生成される数については、基底に含まれない素数のみを因数として考えれば済むことになります。これはあたかも、生成された数が既に検証され、基底に含まれるどの素数でも割り切れないことが分かっているかのようです。これらの操作はすべて冗長になり、実行されなくなるため、これは最適化と言えるでしょう。

この手法は、素数探索、あるいは一般的なふるい分けにおいて、素数候補となる数の数が削減されます。基底が{2, 3}の場合、削減される数は全体の1/3 < 34%です。これは、候補となる数の2/3が自動的に除外されることを意味します。基底を大きくすると、この割合はさらに減少します。例えば、基底が{2, 3, 5}の場合、8/30 < 27% 、基底が{2, 3, 5, 7}の場合、 48/210 < 23%になります。

ホイールが大きくなるほど、必要な計算リソースが大きくなり、追加の改善は小さくなるため、収益は急速に減少します。

導入

1以上の自然数は1を繰り返し加算することで数えられます。

1、2、3、4、5、...

それぞれ2つの数の範囲で考えると、2の繰り返し加算によって列挙されます。

1、2; 3、4; 5、6; ...

このようにして生成される2番目の数字はすべて偶数になります。つまり、2の繰り返し加算によってオッズが生成されます。

1 ; 3 ; 5 ; 7 ; ...

 3つの数字それぞれの範囲で考えると、2 ×  3 = 6 の繰り返し加算によって列挙されます。

1、3、5 ; 7、9、11 ; ...

これらの3つ組の2番目の数字はすべて3の倍数になります。これは、3 + 6k の形式の数字がすべて3の奇数倍であるためです。したがって、最初の2つの素数 (2 と 3) と互いに素な数字はすべて、{1, 5} から始めて 6 を繰り返し加算することによって生成されます。

1、5 ; 7、11 ; 13、17 ; ...

同じシーケンスは、2  ×  3  ×  5 = 30を繰り返し加算することによって生成でき、それぞれ2 つの数字からなる5 つの連続する範囲を、 1 つの10 個の数字の結合された範囲に変換します。

1、5、7、11、13、17、19、23、25、29、31、35、37、...

これらの 6 互いに素な数 10 個のうち 2 個は 5 の倍数であるため、残りの 8 個は 30 互いに素になります。

1、7、11、13、17、19、23、29、31、37、41、43、47、49、...

これは当然一般化されます。

上記は最初の 3 つのホイールを示しています。

  • {1}（1 = 2 − 1 の数を含む）の「円周」は 2 で、2 を繰り返し加算することで 2 互いに素な数列を生成します。
  • {1, 5}（2 = (2 − 1)  ×  (3 − 1) の数を含む）の「円周」は 2  ×  3 = 6 であり、6 を繰り返し加算することで 6 互いに素な数のシーケンスを生成します。
  • {1、7、11、13、17、19、23、29}（8 = (2−1)  ×  (3−1)  ×  (5−1) 個の数を含む）の「円周」は 2  ×  3  ×  5 = 30 であり、30 を繰り返し加算することで 30 互いに素な数のシーケンスを生成します。

これらのホイールの別の表現は、上に示したように、ホイールの数字を連続する数字の差を表す循環リストに変換し、これらの増分を最後に生成された数字に無限に繰り返し加算することで、1から始まるシーケンスを生成するというものです。これは、ホイールを転がすというメタファーに最も近いものです。例えば、{1, 7, 11, 13, 17, 19, 23, 29, 31}は{6, 4, 2, 4, 2, 4, 6, 2}に変換され、シーケンスは次のように生成されます。

n =1; n +6=7; n +4=11; n +2=13; n +4=17; n +2=19; n +4=23; n +6=29; n +2=31; n +6=37; n +4=41; n +2=43;等

典型的な例

最初の 3 つの素数 {2、3、5} を基数として、ホイールの「最初の回転」は次のようになります。

7、11、13、17、19、23、29、31。

2ターン目は、1ターン目の数値に基数の積で ある30を加算することで得られます。3ターン目は、2ターン目に30を加算することで得られます。以下同様に続きます。

この方法を実行するために、ホイールの連続する２つの要素間の増分、すなわち

増分 = [4, 2, 4, 2, 4, 6, 2, 6],

各ターン後も同じままです。

以下に提案する実装​​では、補助関数div(n,k)を使用します。この関数は、 nがkで割り切れるかどうかを判定し、割り切れる場合はtrue を、割り切れない場合はfalse を返します。この実装では、因数分解する数はnであり、プログラムはnの最小の約数を返します。素数の場合は n自身を返します。

div( n , 2) = true の場合、  2 を
返します。 div( n , 3) = true の場合、 3 を
返します。 div( n , 5) = true の場合、 5 を
返します。 k  := 7; i  := 0
 while k * k ≤ n div( n , k ) = true の場合、kを返します。k  := k + inc[ i ]
     i < 7の場合、 i  := i + 1それ以外の場合、 i  := 0
 nを返します。

整数の完全な因数分解を得るには、計算を最初からやり直すことなく継続することができます。これは、関数add が最初の引数を2番目の引数（リストである必要があります）の末尾に追加すること で、完全な因数分解を行う次のプログラムにつながります。

因子:= []
 div( n ,2) = true の場合、
    因子 := add(2, 因子)
    n  := n / 2
 div( n , 3) = true の場合、
    因子 := add(3, 因子)
    n  := n / 3
 div( n , 5) = true の場合、
    因子 := add(5, 因子)
    n  := n / 5
 k  := 7; i  := 0
 while  k * k ≤ n  div( n , k ) = true の場合、
    add  
        ( k , factors)
         n  := n / kそれ以外の場合、 k  := k + inc[ i ]
         i < 7 の場合、i  := i + 1の場合、 i  := 0
 n > 1の場合、 add( n , factors)
を実行します。factors を
返します。

別のプレゼンテーション

ホイール因数分解は、単純な数式と最初の素数の非常に小さなリストから、ほとんどが素数のリストを生成するために使用されます。これらのリストは、試し割りやふるい分けに使用できます。これらのリストのすべての数が素数であるとは限らないため、これを行うと非効率的な冗長操作が導入されます。ただし、生成器自体は、純粋な素数のリストを保持する場合と比較して、非常に小さなメモリしか必要としません。最初の素数の小さなリストは、リストの残りを生成するアルゴリズムの完全なパラメータを構成します。これらの生成器はホイールと呼ばれます。各ホイールは無限の数のリストを生成できますが、ある点を超えると、数はほとんど素ではなくなります。

この手法は、素数ホイールふるいとして再帰的に適用することで、より精度の高いホイールを生成することができます。ホイール因数分解、ホイール因数分解を用いたふるい、そしてホイールふるいに関する多くの決定的な研究は、ポール・プリチャード[1] [2] [3] [4]によって行われ、一連の異なるアルゴリズムが定式化されました。因数分解ホイールの使い方を視覚的に理解するために、まず隣の図に示すように、円の周りに自然数を書きます。スポークの数は、素数が少数のスポークに集まる傾向があるように選択されます。

サンプルのグラフィカル手順

  1. 因数分解ホイールの基礎となる最初の素数をいくつか見つけます。これらは既知であるか、あるいはより小さな因数分解ホイールの過去の適用例、あるいはエラトステネスの篩を用いて素早く見つけることで決定されている可能性があります。
  2. 基本素数を掛け合わせると、因数分解ホイールの円周である結果nが得られます。
  3. 1からnまでの数字を円の中に書きます。これが車輪の1回転を表す最も内側の円になります。
  4. 最も内側の円の数字 1 からnまでから、手順 2 で適用した手順 1 の基本素数の倍数をすべて消去します。この合成数の消去は、エラトステネスのふるいなどのふるいを使用するか、より小さな因数分解ホイールを適用することで実現できます。
  5. これまでに書いた円の数をxとし、最も内側の円の周りの同心円状にxn + 1からxn + nを書き続けます。xn + 1は( x −1) n +1と同じ位置になります。
  6. 最大の回転円が素数かどうかをテストする最大の数値にまたがるまで、手順 5 を繰り返します。
  7. 数字の1を削除します。
  8. 手順 1 で見つけて手順 2 で適用した素数のスポークを、最も内側の円 (円 1) の素数を消さずに、すべての外側の円で消します。
  9. 手順 8 で基本素数のスポークを削除したのと同じ方法で、手順 4 で内側の円 1 から削除したすべての素数の倍数のスポークを削除します。
  10. ホイールに残っている数はほとんどが素数です（これらはまとめて「相対的に」素数と呼ばれます）。エラトステネスの篩などの他の方法や、より大きな因数分解ホイールをさらに適用して、残りの非素数を取り除きます。

例

n = 2 × 3 = 6のホイール因数分解
  1. 最初の 2 つの素数、2 と 3 を見つけます。
  2. n = 2 × 3 = 6
  3. 1 2 3 4 5 6
  4. 2 と 3 の因数である 4 と 6 を削除します。3 の因数である 6 は既に削除されています。 
    1 2 3   4   5   6
  5. x = 1.
    xn + 1 = 1 ⋅ 6 + 1 = 7.
    ( x + 1) n = (1 + 1) · 6 = 12.
    7 を 1 に合わせて 7 から 12 まで書きます。 
      1 2 3   4   5   6 
  7 8 9 10 11 12
  6. x = 2.
    xn + 1 = 2 ⋅ 6 + 1 = 13.
    ( x + 1) n = (2 + 1) · 6 = 18.
    13 から 18 までを書きます
    。次の数行についても繰り返します。 
      1 2 3   4   5   6
  7 8 9 10 11 12
 13 14 15 16 17 18
 19 20 21 22 23 24
 25 26 27 28 29 30
  7. ふるい分け 
      1   2 3   4   5   6 
  7   8   9 10 11 12
 13 14  15 16 17 18
 19 20  21 22 23 24
 25 26  27 28 29 30
  8. ふるい分け 
      1   2 3   4   5   6 
  7   8   9  10 11 12 13 
 14 15  16  17 18 19 
 20 21  22  23 24 25 
 26 27  28  29 30
  9. 結果のリストには素数でない数25（5 2 ）が含まれています。ふるいなどの他の方法を使用してこれを除去して、
    2 3 5 7 11 13 17 19 23 29

5 サイクルの次の素数を使用し、その結果のリストからその素数の倍数（そしてその素数のみ）を除去することで、ステップ 4 に従って、2、3、5 を基本素数とする因数分解ホイールの基本ホイールが得られることに注意してください。これは、前の {2,3} 因数分解ホイールより 1 つ進んだホイールです。次に、7 サイクルの次の素数を使用し、ステップ 10 の結果のリストから 7 の倍数のみを除去する（この場合とそれ以降のすべてのケースでは、いくつかの「相対的」素数、つまり真の完全修飾素数ではない素数は残します）ことで、さらに次の進んだホイールが得られます。必要に応じてこれらの手順を再帰的に繰り返すことで、より大きなホイールが得られます。

分析とコンピュータ実装

正式には、この方法は以下の知見を活用します。第1に、基本素数の集合とその（無限の）互いに素な集合を結合したものが素数のスーパーセットであるということです。第2に、互いに素な無限集合は、2と基本集合の積の間の基本集合までの互いに素な集合から簡単に列挙できるということです。（1には特別な処理が必要であることに注意してください。）

上記の例に見られるように、ステップ 4 から 10 までの再帰手順を繰り返し適用した結果は、任意のふるい分け範囲 (その範囲まで切り捨て可能) にまたがるホイール リストになる可能性があり、結果のリストには、最後に使用した基本素数の 1 より大きい素数の倍数のみが含まれます。

ホイールがふるい分け範囲の望ましい上限に達すると、それ以上のホイールの生成を停止し、そのホイールの情報を使用して、エラトステネスのふるいタイプの手法で最後のホイールリストから残りの合成数をカリングすることができますが、ホイール固有のギャップパターンを使用して冗長なカリングを回避します。合成数が繰り返しカリングされないという事実 (次のセクションで証明されます) に基づいて、いくつかの最適化を行うことができる場合があります。残りの各合成数は正確に 1 回カリングされます。代わりに、望ましいふるい範囲の平方根までの素数を使用して、切り捨てられたホイールリストを生成し続けることもできます。この場合、ホイール内の残りのすべての数値表現は素数になります。ただし、この方法は合成数を複数回カリングしないという点で効率的ですが、通常考慮されるカリング操作以外の多くの時間が、後続のホイールスイープの処理で失われるため、処理時間が大幅に長くなります。因数分解ホイールによる合成数の消去は、次の原理に基づいています。k > nという数が与えられたとき、k mod nかつnが互いに素でない場合、 kは素数ではないことが分かります。このことから、ホイールふるいが消去する数の割合は（すべてを物理的に消去する必要はなく、小さいホイールから大きいホイールにコピーする操作で多くの数が自動的に除去されます）、1 − φ ( n ) / nと決定できます。これはふるいの効率でもあります。

知られているのは

リム 無限大 φ （ n ） n ログ ⁡ ログ ⁡ n ＝ e − γ 〜 0.56145948 、 {\displaystyle \lim \inf {\frac {\varphi (n)}{n}}\log \log n=e^{-\gamma }\sim 0.56145948,}

ここでγはオイラー定数である。[5]したがって、nが無限大に増加するにつれてφ ( n )/ nはゆっくりとゼロになり、この効率はnが無限大になると非常にゆっくりと100%に上昇することがわかる。φの特性から、 xより小さい最も効率的なふるいはn = p 1 p 2 … p i < xかつnp i +1 ≥ xとなるふるいであることが容易にわかる（つまり、最後のホイールが通過するか、ふるい分け範囲内の最大数を含むのに十分な円周を持つようになったときにホイール生成を停止できる）。

コンピュータで最大限に活用するには、nより小さく、かつnと互いに素である数を集合としてまとめる必要があります。いくつかの観察結果から、この集合は簡単に生成できます。

  1. S 1 = {1}から始めます。これはn = 1で、最初の素数が 2 である集合です。この初期集合は、車輪の円周が 1 であるため、2 から始まるすべての数が「相対的」素数として含まれることを意味します。
  2. 次のセットはS 2 = {1}であり、これはすべての奇数について 3 から始まり、2 の因数が除去されます (円周 2)。S 6 = {1,5}は、上記の例の初期ベースホイールと同様に、2 と 3 の因数が除去されます (円周 6)。
  3. S n + k を、 S nの各要素にkが追加された集合とします。
  4. すると、S np i +1 = F p i +1 [ S n ∪ S n + n ∪ S n + 2 n ∪ … ∪ S n + n ( p i +1 − 1)]となり、ここでF xはxの倍数をすべて削除する演算を表します。
  5. 1 とp i +1 は、 n > 2 のときにS nの 2 つの最小値になるため、素数を個別に計算する必要がなくなります。ただし、アルゴリズムでは、後続のセットに含まれなくなったすべての除去された基本素数の記録を保持する必要があります。
  6. 円周がn > 2であるすべての集合はn / 2 を中心に対称であり、必要な記憶領域を削減します。以下のアルゴリズムはこの事実を利用しませんが、各集合内の連続する数字間の間隔が中間点を中心に対称であるという事実に基づいています。

参照

参考文献

  1. ^ プリチャード、ポール、「線形素数ふるい：家系図」、科学、コンピュータプログラミング 9：1（1987）、17–35頁。
  2. ^ ポール・プリチャード「素数を見つけるための亜線形加法ふるい」Communications of the ACM 24 (1981), 18–23. MR  0600730
  3. ^ ポール・プリチャード「ホイールふるいの説明」Acta Informatica 17 (1982), 477–485. MR  0685983
  4. ^ ポール・プリチャード「高速コンパクト素数ふるい（その他）」『アルゴリズムジャーナル4』（1983年）、332-344頁。MR  0729229
  5. ^ ハーディ、GH ;ライト、EM（1979）、数論入門（第5版）、オックスフォード大学出版局、thm. 328、ISBN 978-0-19-853171-5
  • ホイール因数分解
  • ポール・プリチャードによる改良された増分素数ふるい
  • 素数コード
「https://en.wikipedia.org/w/index.php?title=Wheel_factorization&oldid=1279299441」より取得