興味がつきないメルセンヌ素数

メルセンヌ数とは、正の整数kに対して$2^k-1$で表すことができる数をメルセンヌ数といいます。50億までのメルセンヌ数を計算すると、次の通りになります。

k=1
temp=0
mersenn=[]
while temp<5_000_000_000:
   temp=2**k-1
   mersenn.append(temp)
   k+=1 
print(mersenn,end=' ')  
print(len(mersenn),'個')

[1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727, 268435455, 536870911, 1073741823, 2147483647, 4294967295, 8589934591] 33 個

最初は1，3，7とたくさん見つかりますが、べき乗していることからkが大きくなるにしたがい巨大化し、50億の中でたかだか33個しかありません。

こんなメルセンヌ数ですが、興味深い定理があります。

メルセンヌ数のうち、素数になるものをメルセンヌ素数といいます。そこで、前節で求めたメルセンヌ数を素数（mersenn_p）と合成数（mersenn_c）に分けます。メルセンヌ数を見るときに、小さい数字から数えての順番が大切になります。そこで、k番目のメルセンヌ数をM_kとして、kとM_kを要素とする辞書形式にします。

import sympy
mersenn_p={}
mersenn_c={}
for cnt,i in enumerate(mersenn):
   if sympy.isprime(i):
       mersenn_p[cnt+1]=i
   else:
       mersenn_c[cnt+1]=i
print(mersenn_p)
print(mersenn_c)
print('素　数:',len(mersenn_p),'個')
print('合成数:',len(mersenn_c),'個')

{2: 3, 3: 7, 5: 31, 7: 127, 13: 8191, 17: 131071, 19: 524287, 31: 2147483647}
{1: 1, 4: 15, 6: 63, 8: 255, 9: 511, 10: 1023, 11: 2047, 12: 4095, 14: 16383, 15: 32767, 16: 65535, 18: 262143, 20: 1048575, 21: 2097151, 22: 4194303, 23: 8388607, 24: 16777215, 25: 33554431, 26: 67108863, 27: 134217727, 28: 268435455, 29: 536870911, 30: 1073741823, 32: 4294967295, 33: 8589934591}
素　数: 8 個
合成数: 25 個

上記のことから、メルセンヌ数が素数の時には、その順序kも素数になります。ただし、kが素数であっても、メルセンヌ数が素数とは限りません。k=11,23,29の場合がこれに当たります。このほかにも、興味深い定理がたくさんあります。

詳しくは次をご覧ください。

Pythonでメルセンヌ素数を計算する