・メルセンヌ数 うんざりはちべえ氏
メルセンヌ数は素数であるので、素数候補式 30n+P に含まれる。
実際、４番目以降のメルセンヌ数は、30n+1 か 30n+7 である。また、メルセンヌ数は、2^a-1
であり、等比級数の和の公式から、
（2^a-1）/（2-1）=1+2+2^2+2^3+2^4+・・・+2^(a-1) より、
2^a-1=1+2+2^2+2^3+2^4+・・・+2^(a-1)
これより、メルセンヌ数は、２進数では、1が並んだ数である。
たとえば、1が並んだ数は、111111111（9個並んだ数）÷111＝1001001 より、
111111111＝111x1001001となる。
一般に1が、n個並んだ数において、nが素因数分解できれば、たとえば、n=15=3x5 より、
111 111 111 111 111（15個並んだ数）÷111＝1 001 001 001 001 より、111(3個)で割り切
れる。また、11111 11111 11111（15個並んだ数）÷11111＝1 00001 00001 より、
11111(5個)でも割り切れる。
さて、メルセンヌ数と 30n+1 は、 2^a-1=30n+1 から、2^a-2=30n すなわち、2^(a-1)-1=15n
メルセンヌ数はaが素数であるので、a-1は偶数の合成数である。
2^(a-1)-1=1+2+2^2+2^3+2^4+・・・+2^(a-2) より、2^(a-1)-1は、1が偶数個並んだ数であり、
その数は合成数である。
そこで、15は、2進数1111であるから、2^(a-1)-1は、1が偶数個並んだ数であり、4個並ん
だ数で割り切れる。つまり、a-1は、4の倍数である。
また、メルセンヌ数と 30n+7 は、2^a-1=30n+7 から、2^a-8=30n すなわち、2^(a-1)-4=15n
から、 2^2{2^(a-3)-1}=15n より、nは4の倍数であり、
2^(a-3)-1=1+2+2^2+2^3+2^4+・・・+2^(a-4)
より、2^(a-3)-1は、1が偶数個並んだ数であり、その数は合成数である。
そこで、15は、2進数1111であるから、2^(a-3)-1は、1が偶数個並んだ数であり、4個並ん
だ数で割り切れる。つまり、a-3は、4の倍数である。
さて、30n+Pには、P=11,13,17,19,23,29もあるが、2^a-1=30n+P で、P+1=2q として、
2^a-2q=30n すなわち、2^(a-1)-q=15n
ここで、P=11,13,17,19,23,29のとき、q=6,7,9,12,15で、2^(a-1)-q=15n を成り立たせることは
できない。
メルセンヌ数は、1が並んだ数であるが、wikipediaより、7以上の
2^3-1=30n+7
2^5-1=30n+1
2^7-1=30n+7
2^13-1=30n+1
2^17-1=30n+1
2^19-1＝30n+7
2^31-1=30n+7
2^61-1=30n+1
2^89-1=30n+1
2^107-1=30n+7
2^127-1=30n+7
2^521-1=30n+1
2^607-1=30n+7
2^1279-1=30n+7
2^2203-1=30n+7
2^2281-1=30n+1
2^3217-1=30n+1 |
|
2^4253-1=30n+1
2^4423-1=30n+7
2^9689-1=30n+1
2^9941-1=30n+1
2^11213-1=30n+1
2^19937-1=30n+1
2^21701-1=30n+1
2^23209-1=30n+1
2^44497-1=30n+1
2^86243-1=30n+7
2^110503-1=30n+7
2^132049-1=30n+1
2^216091-1=30n+7
2^756839-1=30n+7
2^859433-1=30n+1
2^1257787-1=30n+7
2^1398269-1=30n+1 |
|
2^2976221-1=30n+1
2^3021377-1=30n+1
2^6972593-1=30n+1
2^13466917-1=30n+1
2^20996011-1=30n+7
2^24036583-1=30n+7
2^25964951-1=30n+7
2^30402457-1=30n+1
2^32582657-1=30n+1
2^37156667-1=30n+7
2^42643801-1=30n+1
2^43112609-1=30n+1
2^57885161-1=30n+1
2^74207281-1=30n+1
2^77232917-1=30n+1
2^82589933-1=30n+1 |
以上からして、7以上のメルセンヌ数は、30n+P型の素数で、30n+1、30n+7 しかとらない。
ＨＮ「通りすがり」さんからのコメントです。（令和５年３月４日付け）
さて、30n+Pには、P=11,13,17,19,23,29もあるが、2^a-1=30n+P で、P+1=2q として、
2^a-2q=30n すなわち、2^(a-1)-q=15n
ここで、P=11,13,17,19,23,29のとき、q=6,7,9,12,15で、2^(a-1)-q=15n を成り立たせることは
できない。
P=11,13,17,19,23,29のとき、P+1=2qに代入すると、q=6,7,9,10,12,15で、2^(a-1)-q=15nに代
入すると、2^(a-1)＝15n＋6,9,10,12,15の場合は、３または５でくくれるのであり得ませんが、
2^(a-1)＝15n＋7の場合は、「2^(a-1)-q=15nを成り立たせることはできない」証明はされた
のでしょうか。一応、n=1000くらいまではプログラミングを組んでありませんでしたが．．．。
for n in range(1,1001):
expr = 15*n + 7
if list(bin(expr)).count('1') == 1:
print('OK')
else:
print('NG')
らすかるさんからのコメントです。（令和５年３月４日付け）
2^1、2^2、2^3、2^4、… を15で割った余りは、2、4、8、1、2、4、8、1、… となりますので、
15n+7になることはないですね。
また、元の問題は最初から mod 30 で考えると簡単です。
2^1、2^2、2^3、2^4、… を30で割った余りは、2、4、8、16、2、4、8、16、… となりますので、
2^a-1=30n+1,3,7,15 しかあり得ません。よって、素数になる場合は、30n+1、30n+7 のみです。
ＨＮ「通りすがり」さんからのコメントです。（令和５年３月５日付け）
らすかるさん、ありがとうございます。勉強になりました。
さて、メルセンヌ数と 30n+1 は、 2^a-1=30n+1 から、2^a-2=30n すなわち、2^(a-1)-1=15n
メルセンヌ数はaが素数であるので、a-1は偶数の合成数である。
2^(a-1)-1=1+2+2^2+2^3+2^4+・・・+2^(a-2) より、2^(a-1)-1は、1が偶数個並んだ数であり、
その数は合成数である。
そこで、15は、2進数1111であるから、2^(a-3)-1は、1が偶数個並んだ数であり、4個並ん
だ数で割り切れる。つまり、a-3は、4の倍数である。
２進法を使わない場合は、
2^a-1=30n+1 から、2^a-2=30n よって、2^(a-1)-1=15n から、 2^(a-1)-1=(2^4-1)n
因数分解の公式より、2^4m-1=(2^4)^m-1=(2^4-1){(2^4)^(m-1)+(2^4)^(m-2)＋…＋１}
よって、a-1は４の倍数ですね。
以下、工事中！
