前のトピック
次のトピック
前回, 偶数の完全数はメルセンヌ素数を使って表すことができるという定理を証明しました｡ 記憶を辿るとメルセンヌ素数とは\(2^p-1\)という形で書ける素数のことでした｡ 今回はこのメルセンヌ素数について考察しましょう｡
まずはPythonを使って, メルセンヌ素数をいくつか発見してみましょう｡
from sympy import isprime # 素数判定のisprimeをsympyモジュールからインポート
def mersenne_print (x): # x以下のメルセンヌ素数を出力する関数
p = 1 # メルセンヌ素数内の2の指数
M = 2 ** p - 1 # メルセンヌ素数の候補
while M < x: # Mがxより小さい限り次を繰り返す
if isprime(M): # Mが素数なら
print(M) # Mを出力する
p += 1 # 次のpの値
M = 2 ** p - 1 # 新しいMの値与えられた数\(x\)以下の\(2^p-1\)の形の自然数をisprimeで素数判定し, 素数なら出力するという関数です｡ では, いきなりですが\(x\)に100億を入れた結果を見てみましょう｡
## 3
## 7
## 31
## 127
## 8191
## 131071
## 524287
## 2147483647すると, あっという間に8個のメルセンヌ素数を見つけられました｡ このコードはメルセンヌ素数を発見するたびにprintしていましたが, 少し改造して発見したメルセンヌ素数を一つのリストとして返すコードを書いてみましょう｡
append()ここでPythonのリストに関する便利な機能を紹介しましょう｡ 既存のリストに新しい要素を追加したいときに使えるメソッドです｡ リストの後に.appned()を書き, カッコの中に追加したい要素を書けばOKです｡ 例えば次のように使えます｡
実行結果は次の通り4が加わったリストになります｡
## [1, 2, 3, 4]前回 perfects(x)という完全数を探し出すプログラムを書きました｡ そのプログラムでは4つ目の完全数\(8128\)まで見つけ出すことができましたが, 次の完全数を発見するには時間がかかり過ぎました｡
完全数を約数の総和を計算して求めるのではなく, メルセンヌ素数から完全数を作り出す方法も学びました｡ 先ほど\(8\)個のメルセンヌ素数を発見したので, これらのメルセンヌ素数から完全数を作ってみましょう｡
\(M_p = 2^p-1\)がメルセンヌ素数のとき\(2^{p-1}M_p\)が完全数になるのでした｡ 上のプログラムは\(M_p\)を出力していますが, \(p\)自体を出力していないので\(2^{p-1}\)を\((M_p+1)/2\)から求める必要があります｡ (もちろん上のプログラミングを\(p\)を出力するように修正してもOKです｡)
def mersenne_to_perfect (x): # x以下のメルセンヌ素数に対応する完全数のリストを出力する
l = [] # 完全数を入れるリスト
for mer in mersenne_list(x):
power2 = (mer + 1)// 2 # 完全数の2のべき
perfect = power2 * mer # 完全数
l.append(perfect)
return l## [6, 28, 496, 8128, 33550336, 8589869056, 137438691328, 2305843008139952128]8個の対応する完全数が得られました｡ このように完全数を直接求めようとするよりも, メルセンヌ素数を見つけてからそれを完全数に変換するほうが効率がよいことがわかりました｡
ただ, 上のメルセンヌ素数を発見するアルゴリズムも効率のよいものとは言えません｡ そのアルゴリズムでは\(2^p-1\)が\(x\)より小さい範囲のすべての自然数\(p\)に対して\(M_p\)の素数判定をしていました｡ 実は\(M_p\)が素数になるためには\(p\)自身も素数である必要があるのです｡ この事実を用いると, 調べる候補が減り効率がよくなります｡ まずはこの事実を証明しましょう｡
もし$M_p=2^p-1$が素数なら$p$も素数である｡
もしも仮に\(p\)が合成数だとします｡ すると\(p=ab\)となるような整数\(a > 1, b > 1\)が存在します｡ すると \[\begin{align*}
M_p &= 2^{p} – 1 = 2^{ab} -1\\
&= (2^a)^b -1\\
&= (2^a-1)(1+2^a+(2^a)^2+\cdots+(2^a)^{b-1}).
\end{align*}\] ここで最後の等式は前回の補題を\(x=2^a\)として適用して得られます｡
さて, \(a >1, b>1\)ですので, 最後の式は1より大きい整数の積ということになります｡ しかしこれは\(M_p\)が合成数ということになり\(M_p\)が素数であることに矛盾します｡ ゆえに\(p\)は素数でなくてはならないことがわかりました｡ 以上で証明を終わりにしたいと思います｡
今証明した定理の逆は必ずしも成り立たないことに注意です｡ 例えば\(p=11\)は素数ですが, \(M_p=2^{11}-1=2047=23\cdot 89\)と素因数分解できることから素数ではありません｡
では上の定理をアルゴリズムに取り入れて改良してみましょう｡
from sympy import isprime
def mersenne_list2 (x): # x以下のメルセンヌ素数のリストを返す関数
p = 3 # メルセンヌ素数内の2の指数
M = 2 ** p - 1
l = [3] # 発見したメルセンヌ素数を収納するリスト｡ 3だけ予め入れておく｡
while M < x:
if isprime(p): # もしpが素数で
if isprime(M): # Mも素数なら
l.append(M) # メルセンヌ素数をリストに追加
p += 2 # 次のpの値
M = 2 ** p - 1
return l改良版では\(p\)の素数判定をしなくてはなりませんが, \(M_p\)にくらべて\(p\)はとても小さいので素数判定もその分速いです｡ また\(p=2\)のときのメルセンヌ素数\(3\)は既知のものとしてリストに入れておき\(p=3\)から始めて\(2\)ずつ増やすことで奇数のみをチェックしていっています｡
\(2^p-1\)の形の自然数をメルセンヌ素数かどうかを判定するリュカ・レーマーのテストと呼ばれる判定法があります｡ これはメルセンヌ素数を発見することに特化した素数判定法であるので, 任意の自然数に対しての素数判定アルゴリズムに比べて高速です｡このように速度面で有利なリュカ・レーマーのテストを使って多くの巨大な素数が発見されてきました｡ 歴代の世界一大きい素数にはメルセンヌ素数が多数含まれています｡
2018年9月の時点での世界最大の確認されている素数はメルセンヌ素数で \[M_{77,232,917} = 2^{77,232,917}-1\] という\(23,249,425\)桁もある巨大な素数です｡ 参考:ウィキペディア
リュカ・レーマーのテストは｢合同式(mod)｣を学んでからその応用として紹介したいと思います｡
ここではメルセンヌ素数やその類似の数に関する問題を解いてみよう｡
\(2^n-1\)と\(2^n+1\)が同時に素数になるような自然数\(n\)をすべて見つけてください｡
この問題はちょっとしたことで見通しがよくなります｡ ポイントは, これらの数の間には\(2^n\)という自然数があるということに注目することです｡ \(2^n-1\), \(2^n\), \(2^n+1\)は3つの連続した自然数です｡ 3つの連続した自然数のうち必ず一つは3の倍数の数が含まれます｡ このとき真ん中の数\(2^n\)は\(3\)で割り切れません｡ (なぜならすでに素因数分解されていて\(2\)しか素因数を含まないからです｡)
つまり, \(2^n-1\)か\(2^n+1\)のどちらかが必ず3の倍数になります｡ \(3\)の倍数で素数なのは\(3\)だけです｡ もし\(2^n-1=3\)なら, \(n=2\)となります｡ この場合には\(2^2+1=5\)も素数となるので\(2^n-1\)か\(2^n+1\)の両方とも素数になることがわかりました｡ \(2^n+1=3\)の場合には\(n=1\)であり, \(2^1-1=1\)は素数になりません｡ もし\(n>2\)ならば片方が素数であっても, もう片方は\(3\)以外の\(3\)の倍数となることから合成数です｡
よって\(2^n-1\)と\(2^n+1\)が同時に素数になるような自然数は\(n=2\)に限ることが証明できました｡ これで証明を終わりにしたいと思います｡
\(2^n-1\)の形をした(素数とは限らない)自然数をメルセンヌ数と呼びます｡ もちろん素数のときにはメルセンヌ素数になります｡ メルセンヌ素数のときと同じ記号を使って\(M_n=2^n-1\)と書きましょう｡
\(n\)が\(30\)までのメルセンヌ数を素因数分解してみましょう｡ また\(n\)を素数に限った場合にも同じようにメルセンヌ数を素因数分解してみてください｡ このときは\(n\)が\(50\)以下の素数としてみましょう｡ これらの素因数分解のデータから何か読み取れることがないか考えて, 予想を作ってみてください｡
問題文では\(n=30\)で固定されていますが, 柔軟に使えるように関数を作ってみましょう｡
from sympy import factorint
def mersenne_numbers (x):
for n in range(1, x + 1):
mer = 2 ** n - 1
fac = factorint(mer)
print(f"M_{n}の素因数分解は{fac}")
mersenne_numbers (30)## M_1の素因数分解は{}
## M_2の素因数分解は{3: 1}
## M_3の素因数分解は{7: 1}
## M_4の素因数分解は{3: 1, 5: 1}
## M_5の素因数分解は{31: 1}
## M_6の素因数分解は{3: 2, 7: 1}
## M_7の素因数分解は{127: 1}
## M_8の素因数分解は{3: 1, 5: 1, 17: 1}
## M_9の素因数分解は{7: 1, 73: 1}
## M_10の素因数分解は{3: 1, 11: 1, 31: 1}
## M_11の素因数分解は{23: 1, 89: 1}
## M_12の素因数分解は{3: 2, 5: 1, 7: 1, 13: 1}
## M_13の素因数分解は{8191: 1}
## M_14の素因数分解は{3: 1, 43: 1, 127: 1}
## M_15の素因数分解は{7: 1, 31: 1, 151: 1}
## M_16の素因数分解は{3: 1, 5: 1, 17: 1, 257: 1}
## M_17の素因数分解は{131071: 1}
## M_18の素因数分解は{3: 3, 7: 1, 19: 1, 73: 1}
## M_19の素因数分解は{524287: 1}
## M_20の素因数分解は{3: 1, 5: 2, 11: 1, 31: 1, 41: 1}
## M_21の素因数分解は{7: 2, 127: 1, 337: 1}
## M_22の素因数分解は{3: 1, 23: 1, 89: 1, 683: 1}
## M_23の素因数分解は{47: 1, 178481: 1}
## M_24の素因数分解は{3: 2, 5: 1, 7: 1, 13: 1, 17: 1, 241: 1}
## M_25の素因数分解は{31: 1, 601: 1, 1801: 1}
## M_26の素因数分解は{3: 1, 2731: 1, 8191: 1}
## M_27の素因数分解は{7: 1, 73: 1, 262657: 1}
## M_28の素因数分解は{3: 1, 5: 1, 29: 1, 43: 1, 113: 1, 127: 1}
## M_29の素因数分解は{233: 1, 1103: 1, 2089: 1}
## M_30の素因数分解は{3: 2, 7: 1, 11: 1, 31: 1, 151: 1, 331: 1}Pythonの辞書文のここでの読み方を復習しましょう｡ 例として\(6\)番目のメルセンヌ数\(M_6=2^6-1=63=3^2 \cdot 7\)の実行結果をみると{3: 2, 7: 1}となっています｡ コロン:の左側の数字が素因数で, 右側の数字がその素因数が何個必要かを表す指数です｡ つまりこの場合は\(3^2\cdot 7^1\)となっているという意味です｡
次に\(n\)を素数に限った場合にプログラムを改変しましょう｡
from sympy import factorint, isprime
def mersenne_numbers_p (x):
for n in range(1, x + 1):
if isprime(n):
mer = 2 ** n - 1
fac = factorint(mer)
print(f"M_{n}の素因数分解は{fac}")
mersenne_numbers_p (50)## M_2の素因数分解は{3: 1}
## M_3の素因数分解は{7: 1}
## M_5の素因数分解は{31: 1}
## M_7の素因数分解は{127: 1}
## M_11の素因数分解は{23: 1, 89: 1}
## M_13の素因数分解は{8191: 1}
## M_17の素因数分解は{131071: 1}
## M_19の素因数分解は{524287: 1}
## M_23の素因数分解は{47: 1, 178481: 1}
## M_29の素因数分解は{233: 1, 1103: 1, 2089: 1}
## M_31の素因数分解は{2147483647: 1}
## M_37の素因数分解は{223: 1, 616318177: 1}
## M_41の素因数分解は{13367: 1, 164511353: 1}
## M_43の素因数分解は{431: 1, 9719: 1, 2099863: 1}
## M_47の素因数分解は{2351: 1, 4513: 1, 13264529: 1}これらの実行結果から何か読み取って予想を立てることができましたか? ここでは一つの例を紹介します｡ 注目するところは素因数の指数です｡ \(n\)を素数に限って\(M_n\)を素因数分解した結果の指数はすべて\(1\)であることが読み取れます｡ 例えば, \(M_6\)や\(M_{12}\)など\(n\)が合成数の場合には2以上の指数が現れていますが, 素数に限ったデータには指数が1のみです｡ この観測から｢\(n\)が素数のときのメルセンヌ数\(2^n-1\)は平方因子を持たない｣と予想できます｡ (自然数が平方因子を持つとはある素数の二乗で割り切れることです｡)
実はこの予想は未解決問題です｡
次回は整数論を学んでいくのに必須の道具である合同式の計算(mod)を学びます｡ 合同式は上で紹介したリュカ・レーマーのテストや新しい素数判定法など様々な応用を可能にするとても強力で便利な道具ですので, 学ばなければ損する数学です｡