中学数学による双子素数の篩

はじめに

ねこみみです。中学時代双子素数に興味を持っていまして、その時のことを思い出したので記事にしてみようと思います。
そうですね、今から6年前の遺産なのでこれ自体を考えたのが昔な点についてはご了承ください。

訂正

演習について, 残った自然数群$1, 2, \mathbf{3}, 5, 7, 10, 12$と, $3$が含まれているのに対して, 対応する$(17, 19)$の双子素数の組の記述が抜けておりました。
@fujitanozomuさん, ご指摘ありがとうございました。

双子素数とは

双子素数は、 隣り合う2つの素数$p_i, p_{i+1}$があったときにその差が$p_{i+1}-p_i=2$となるようなものを指します。例えば$3$と$5$, $11$と$13$といった感じです。これをすべて過不足なく見つけるための篩を今回作っていきます。

必要な知識

「$n$を自然数とすると, $2, 3$以外の素数はすべて$6n\pm1$で表される」ことさえ理解していればOKです。
初めて知った人は次の証明を見てください。

証明

次のような手順で証明可能である.

1. 自然数を$6$で割ると, 余りは$0$から$5$になる. そのため, 商を$0$以上の整数$n$とすると, 自然数は$6n$, $6n+1$, $6n+2$, $6n+3$, $6n+4$, $6n+5$のどれかで表すことができる.
2. $6n+2$, $6n+4$は, $2$の倍数, $6n+3$は$3$の倍数, $6n$は$6$の倍数であるため, 素数は$6n+1$または$6n+5$の中にしか存在しない.
3. このとき, $n=0$だと$6n+1=1$は素数にはならない. したがって, $6n+1$は$n$が1以上の場合にのみ素数になる可能性がある. これに合わせて, $6n+5$を$6(n+1)-1$と書き直す. すると$n$は0以上の整数のため, $n+1$は自然数であり, さっきの$6n+1$の$n$の範囲と一致させることができた.
4. 以上から, 素数は$n$を自然数とすると$6n\pm1$の中にしか存在しない. ただし, このルールは$5$以上の数にのみ適用されるため, $2, 3$は対象外である.

Step1 素数と非素数の区別

素数は$6n\pm1$で表せます。しかし、$6n\pm1$がすべて素数というわけではありません。そのため、正確に篩にかけるには素数の$6n\pm1$と素数でない$6n\pm1$を区別する必要がありそうです。
さて、$6n\pm1$は$2$の倍数と$3$の倍数ではないということは分かっています。$6n\pm1$を素因数分解するとどうなるでしょうか。素因数は$2$と$3$以外の素数になるはずです。あれ？それってどっかで見ませんでしたか？
そうです。$6n\pm1$を素因数分解するとその素因数はすべて$6n\pm1$で表すことができます。
つまり$6n\pm1$で表される数は、素数$p$、または$(6n_1\pm1)(6n_2\pm1)\cdots$で表される数のどちらか、ということがわかりました。

Step2 素数と素数の積

$(6n_1\pm1)(6n_2\pm1)\cdots$を消去すれば素数がすべて出てくるじゃん！みたいな話になりますが、さらに簡略化していきましょう。そこで, 素数と素数の積$(6m\pm1)(6n\pm1)$を計算してみます。
因数分解の公式を知っていなくても分配法則がわかればこれは計算できますね。

(6m\pm1)(6n\pm1)\\
=6m(6n\pm1)\pm1(6n\pm1)\\
=36mn\pm 6m\pm 6n\pm 1\\
=6(6mn\pm m\pm n)\pm1\\
= 6N\pm1

$(6m\pm1)(6n\pm1)$が$(6N\pm1)$になるということは、$(6n_1\pm1)(6n_2\pm1)\cdots$をすべて消さなくても$(6m\pm1)(6n\pm1)$を篩にかければよいことになります。

Step3 双子素数の篩について考える

素数がどう表されるかについて今まで議論しましたが、双子素数については出てきませんでしたね。双子素数はどう表されるでしょうか。
素数は$6n\pm1$で表されました。双子素数は隣り合う$2$つの素数の差が$2$になる素数でした。$6n\pm1$の中で差が$2$になるような$2$つの数の選び方は、同じ$n$について$(p, q) = (6n-1, 6n+1)$のパターンしかないですね。
そのため、$6n\pm1$が両方素数になるような$n$を求めよう、という問題を解けばよさそうです。

Step4 双子素数の篩概略

では, 自然数$n$に着目します。$6n\pm1$が素数でないときには, $(6m\pm1)(6n\pm1)=(6N\pm1)$の形になるはずです。
そのため, 自然数$n$の中から$N= 6mn \pm m\pm n$のパターンを除去して, 残った$n$について$6n\pm1$を計算すると全て双子素数になります。

Step5 双子素数の篩のアルゴリズム

$N= 6mn \pm m\pm n$をちょっと別の視点で見てみましょう。$m\times n=mn$ですね。
では$mn$から見たら$m$や$n$は正の約数になりそうです。
加えて、もう一つ探索範囲についても考えます。
$6mn \pm m\pm n$の最小値は$m=1$, $n=mn$の時に両方が引き算されるパターンで$5mn-1$になります。そのため, $mn=x$まで探索すると, $5x-1$までの範囲の自然数のテーブルが探索終了となります。
以上からアルゴリズムはこのようになります。

1. $6N+1$までの範囲で双子素数を判定したい
2. $N$以下の最も大きい$5x-1$を探す($x$は自然数)
3. 自然数$n$を$1$から$5x-1$まで書き並べる
4. $i=1$から$i=x$まで以下を繰り返す
   1. $i$のすべての正の約数を小さい順に並べ$a_0, a_2, \cdots a_m-1$とする.
   2. $j=0$から$j=\lceil\frac{m}{2}\rceil-1$まで繰り返す。($\lceil x\rceil$：$x$以上の最小の整数)
      1. $6i+ a_j+ a_{m-j-1}$を書き並べた自然数のリストから削除
      2. $6i+ a_j- a_{m-j-1}$を書き並べた自然数のリストから削除
      3. $6i- a_j+ a_{m-j}$を書き並べた自然数のリストから削除
      4. $6i- a_j- a_{m-j}$を書き並べた自然数のリストから削除
5. リストの中に残った自然数すべてに対して, $6n\pm1$を計算するとそれが双子素数である。

演習 100までの双子素数の篩

1. $97=6\times16+1$までの範囲だけ判定してみます。($N=16$)
2. $N=16$以下の最大の$5x-1$は$14$なので$x=3$とします。
3. $i=1$の時, 約数は$1$のみなので$(m, n)=(1, 1)$だけ考える
   • $6\times 1+1+1 = 8$
   • $6\times 1-1+1 = 6$
   • $6\times 1+1-1 = 6$
   • $6\times 1-1-1 = 4$
   • よって, $4, 6, 8$除外
4. $i=2$の時, 約数は$1, 2$なので$(m, n)=(1, 2)$だけ考える
   • $6\times 2+1+2 = 15$
   • $6\times 2-1+2 = 13$
   • $6\times 2+1-2 = 11$
   • $6\times 2-1-2 = 9$
   • よって, $9, 11, 13, 15$除外
5. $i=3$の時, 約数は$1, 3$なので$(m, n)=(1, 3)$だけ考える
   • $6\times 3+1+3 = 22$
   • $6\times 3-1+3 = 20$
   • $6\times 3+1-3 = 16$
   • $6\times 3-1-3 = 14$
   • よって, $14, 16, 20, 22$除外
6. 結果残った自然数は$1, 2, 3, 5, 7, 10, 12$である
7. $(3, 5)$以外の, $100$までの双子素数は$(5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71, 73)$であることがわかった。

まとめ

駆け足で説明していったため拙いところもありますが, このようにして双子素数は「素数が$6n\pm1$で表される」という条件だけで簡単に篩にかけることが可能になります。
気が向いたら随時更新して詳しくしていこうと思います。ありがとうございました。