素数を調べるプログラムと剰余行列のパターン
目次
筆者について
- 学生ではないため、論文の書き方がわからない
- 不登校であり、必修科目について理解していない
- 数学の知識が浅いため、適切な用語を知らない
目的
結論
- 同一環境下で n=360360 までの最速の計算時間は、エラトステネスの篩が最も速かった
- パターンが面白い
剰余行列
素数は約数に関係するため、まずは約数のパターンを理解することにしました。
「行数を列数で割った余りの行列」を作成し、
結果が0になる（=行数を列数で割り切れる）セルに色を塗った、
「剰余行列」を作成しました。
（この名前が適しているか分かりませんが）
面白いグラフが出てくるので、この中からパターンを研究します。
ちなみに、マイナスの範囲も含めた行列も、
2つ目のシートとして追加してあり、
対称的になっているのがわかります。
直線パターン
まず、1から順に割ることを考えていきます。
（ゼロ除算を除き）すべての数は、1とその数で割り切れます。
行列では1で割ったものが左に縦に並んでいます。
その数で割ったものが斜め45度に並んでいます。
次に、2で割った余りが2列目にあります。
2以降に偶数（=2の倍数）で素数はありません。
3以降も同様で、3以降に3の倍数で素数はありません。
このグラフでは無数の直線があるように見えます。
点線になっている線は、画像編集でなめらかな直線を描くときに似ています。
行列に現れる直線を表現する名前が欲しい。
格子パターン
今回は「1からnまでの自然数の最小公倍数の数列」を使います。
OEIS（=オンライン整数列大辞典）に登録されている整数列として、
類似する数列が他にもあるのですが、
連続する数字の個数が違ったりするので、
今回はA003418を使いますが、
最初の1は使わないので、この数列も少し違います。
誰か、最初の1が入っていない数列を登録して下さい。
今回使う数列は、
1, 2, 6, 12, 60, 60, 420, 840, 2520, 2520, 27720, 27720, 360360, 360360, 360360...
と続いていきます。
行列には無数の次のパターンが縦に繰り返されています。
- 縦1x横1のパターン
- 縦2x横2のパターン
- 縦6x横3のパターン
- 縦12x横4のパターン...
このパターンは、横が数列の番付、縦が数列の値となります。
例えば、1x1のパターン（=1は1で割り切れる）は下に繰り返されるため、
2や3も1で割り切れます。
2x2のパターンは、
1: 0, 1
2: 0, 0
のようになっており、
3: 0, 1
4: 0, 0
といったようにパターンが繰り返されます。
分かりやすいのが、6x3のパターンです。
1: 0, 1, 1
2: 0, 0, 2
3: 0, 1, 0
4: 0, 0, 1
5: 0, 1, 2
6: 0, 0, 0
このパターンから、2からnまでのいずれかの数で割り切れる数は、
2, 3, 4, 6です。
はじめの1-6であれば、2と3は素数ですが、
以降の7-12にあたる、8と9は素数ではありません。
7以降は、1-6のうち上記の条件で割り切れない1と5が素数である"可能性が"あります。
実際、7-12にあたる1と6である、7と11は素数です。
「7以降は6個毎に1番目と5番目が素数である可能性がある」
と考えることで非常に絞り込むことができます。
注意点としては、1は素数に含まれていませんが、パターンには「素数である可能性がある」として含まれていることです。
そして、各パターンの始めと終わりには、直線のパターンがあります。
例えば12x4の始めの、4x4の左上から右下に向かって、4個セルがあります。
反対に12x4の終わりの、4x4の左下から右上に向かって、4個セルがあります。
これも繰り返すため、13以降も続いていきます。
グラフの原点から斜めの直線は、すべてのパターンの原点ということです。
余談ですが、調べてみると、6個毎のパターンは、Wikipediaの「素数性テスト」（
Primality test - Wikipedia）にすでにありました。
注意点としては、パターンは更新されるということです。
6までは2個毎のパターンを使い、12までは6個毎のパターン、60までは12個毎のパターンを使います。
また、このパターンは素数かどうかを計算する手間を最小限に抑えることを目的としています。
そのため、「素数でないこと」と「素数である可能性があること」しか分かりません。
例えば、25は24の次の数で、「素数である可能性（=2から4で割り切れない）」はあるのですが、25は5の倍数ですから、素数ではありません。
これは一種の篩法と言えます。
また、このパターンの周期の前後は素数であることが"多い"ため、双子素数が現れる要因となります。
また、6の前後の5と7、12の前後の11と13、60の前後の59と61は素数です。
しかし、841は29で割り切れてしまいます。
6までは2個毎にパターンがあり、3、5、7と素数があります。
しかし、60までは12個毎にパターンがありますが、
25や35などは素数ではありません。
さらに
このパターンの中も、対称的になっています。
例えば12x4のパターンは、前半の6x4と、後半の6x4が対称的です。
厳密には6番目と12番目を除く5x4と5x4です。
6x3のパターンには対称的な2x3が2つあります。
6の約数に1と2があるので、（1で割った）6と、2で割った3は特徴的です。
また6x3以上でしか、対称的なパターンはありません。
12x4には3で割ったパターンや、60x5には4で割ったパターンがありそうですが、
頭がおかしくなりそうなので割愛します。
マイナスも含め、
パターンが対称的だったり、連続したり、入れ子になっているなど、
とても面白いことになっています。
プログラム
今回のプログラムでは、素数を調べながら前述の格子パターンも同時に調べます。
パターンを更新するタイミングは、例えば7といった任意の数を計算する際に、
その前の数である6が2からその数まで割り切れるかどうか確認し、
2から3で割り切れることがわかると、
それまでの2個毎のパターンの幅が2であるため、
2から3に上がっていることを確認したら、
2から6個毎のパターンに更新することになります。
コードはGitHubにあります。
Node.jsモジュールとして使えるようにしています。
同一環境下での、最速の計算時間は以下の通りです。
n=360360までしかテストしていませんので、
もっとテストすれば早い順が変わるかもしれません。
checkPrime1
2と3からの偶数を総当たりで調べます。
計算時間は 2101 ms と桁違いに遅いです。
checkPrime2
このパターンを応用したコードです。
コードが複雑で、checkPrime1より速く、
他の関数より遅いです。
計算時間は 83 ms です。
checkPrime3
checkPrime2を対照パターンで改良したものです。
checkPrime2より遅くなってしまいました。
計算時間は 87 ms です。
checkPrime4
2と3、5から6個毎に1番目と3番目の数を調べます。
前述のWikipediaにあるコードと同義です。
計算時間は 66 ms です。
checkPrime2、3よりも速く、コードが単純です。
checkPrime5
エラトステネスの篩です。
計算時間は 46 ms で、最も速い結果でした。
