【初めてのJuliaプログラミング】ソフィー・ジェルマン素数を使ってメルセンヌ数の約数を求めてみた。

経緯

以前、こちらの命題を証明しました。

※$2p+1$が素数になるような素数$p$をソフィー・ジェルマン素数といいます。

↓証明はこちらです。
ソフィー・ジェルマン素数とメルセンヌ数

なんとなく、この命題に愛着がわいてきたので、具体的なソフィー・ジェルマン素数で計算してみることにしました。

例えば

• $p=3$の場合：
  $2\cdot 3+1=7$は素数なので、$3$はソフィージェルマン素数であり、$3\equiv 3(\mathrm{mod}4)$を満たす。
  よって、$7$は$2^3-1=7$の約数である。

• $p=11$の場合：
  $2\cdot 11+1=23$は素数なので、$23$はソフィージェルマン素数であり、$11\equiv 3(\mathrm{mod}4)$を満たす。
  よって、$23$は$2^{11}-1=2047$の約数である。

といった感じです。

すると「折角なので、もはや手計算や電卓では計算できなさそうなメルセンヌ数の約数も求めてみたい…」という欲求が生まれてきました。

そこでプログラミングをしてみることにしました。

Julia

今回、「Julia」という言語を使いました。環境構築がとても簡単なので、おすすめです。プログラミング経験の浅い私でも、難なくスタートできました。

Juliaとは？
”アメリカのマサチューセッツ工科大学（MIT）で開発された新しいプログラミング言語である。「コードが簡潔で高水準な記述ができる」こと、「プログラミングの実行速度が速い」ことが特徴で、まさに時代の先端をいく次世代プログラミング言語といえる。”
（進藤裕之・佐藤建太「１から始めるJuliaプログラミング」の裏表紙より）

計算結果

$p$はソフィー・ジェルマン素数で、$p\equiv 3(\mathrm{mod}4)$を満たすものとします。
以下、１行目が$p$、２行目が$2p+1$、３行目が$2^p-1$となっています。つまり、２行目の数が、３行目の数の約数となっています。

※大きな$2^p-1$については、スクロールすると末尾まで見られるようになっています。

$p<{10}^3$

• 3
  7
  $$7$$

• 11
  23
  $$2047$$

• 23
  47
  $$8388607$$

• 83
  167
  $$9671406556917033397649407$$

• 131
  263
  $$2722258935367507707706996859454145691647$$

• 179
  359
  $$766247770432944429179173513575154591809369561091801087$$

• 191
  383
  $$3138550867693340381917894711603833208051177722232017256447$$

• 239
  479
  $$883423532389192164791648750371459257913741948437809479060803100646309887$$

• 251
  503
  $$3618502788666131106986593281521497120414687020801267626233049500247285301247$$

• 359
  719
  $$1174271291386916613944740298394668513687841274454159935353645485766104512557304221731849499192384351515967487$$

• 419
  839
  $$1353842624082429130653522550851115089568572790710847937094960732721983060451965636249987502980536903367866802227247837807116287$$

• 431
  863
  $$5545339388241629719156828368286167406872874150751633150340959161229242615611251246079948812208279156194782421922807143657948315647$$

• 443
  887
  $$22713710134237715329666368996500141698551292521478689383796568724394977753543685103943470334805111423773828800195818060422956300894207$$

• 491
  983
  $$6393341031047152089869511126616404594173128996177860916959553453312761321102879990006386899074031556935325554936640763689877454191182408307282280447$$

• 659
  1319
  $$2392032866531905486790942578809394338145620987608332988883503686824375178865503049616412016019962016447144819201720664620106359620960485637227891297994520232330261783830994590149049944504587400511487$$

• 683
  1367
  $$40131652080904949243476790488282231640246122763238325954424140190648896440865179612073261537762363061729301215028215161995082338334532195000669973530974432754174985283877903733762083113741475809259744657407$$

• 719
  1439
  $$2757826131550993649364364103715456897804056554542556176448634698108099443712107910064330000971904293916892446775667965408323532095584366159791555750475533307061324308088589961496711008293655788792731796366049346060287$$

• 743
  1487
  $$46268644699475435470014199270680622913148582491776246164412857235254375716637876222457838321585848270371190628323884999935972095850551557285913445801770125007762163162852820919462003875720454598226040577701224945512200798207$$

• 911
  1823
  $$17311155196253478792473470072144416162409589179551630037089016513386050438978760195257704640926750732932690575139049592549616764829783999684625661246273604056134014861279398598040994371221141620425498063936264221627122591096883175058256589578798251261609200218857078729474047$$

$p<2\cdot {10}^3$

• 1019
  2039
  $$5617791046444737211654078721215702292556178059194708039794690036179146118921905097897139916325235500660003558745981042426837180275450519452901482207483566386805246669527046414884444362538940441232908842252656430276192208823201965046059784704400851161354703458893321819998351435577491134526104885300757004287$$

• 1031
  2063
  $$23010472126237643618935106442099516590310105330461524130999050388189782503104123280986685097268164610703374576623538349780325090408245327679084471121852687920354290358382782115366684108959500047289994617866880738411283287339835248828660878149225886356908865367627046174713247480125403687018925610191900689563647$$

• 1103
  2207
  $$108663882323950867942188114268741342288279507754539563979881573578225047420339347897643136665660484738388626103630779067800309804345879439769244386742405029775086107995251122654262913153317445846134697284209785412102387486177039652426842288257624643046206077858561591880759072032552928984673183003497469267739721191590324421953323007$$

• 1223
  2447
  $$144439074515673158720724949080128706438642425359068843866970804223953784568476037236842693968934594817599437382358865231016025829751162969207532818595137180147149468098361218351316272857387306572842780868322212928396476266206644984798658523434376214796442240502638021789316943658102671064566780321932176781683346586437073924928642880260067888188419566865785910468804607$$

• 1439
  2879
  $$15211209943731037059535567464979244516021593351122997993978956502918420683608033678661572120429938534772753430839817601321172705542152606726894539332201701529964104344740592610274629092006793100167895669569813779242113100803318231967173863954324760096950315438921638347200882511005772307602751775483856889641263569330789758475141835626731603157336423423303318846414026705334863858529111507416355597577326963750769571320963893861285887$$

• 1451
  2903
  $$62305115929522327795857684336554985537624446366199799783337805835953851120058505947797799405281028238429198052719892895011523401900657077153360033104698169466732971396057467331684880760859824538287700662557957239775695260890391478137544146756914217357108492037823030670134814765079643371940871272381877819970615579978914850714180958727092646532449990341850393994911853385051602364535240734377392527676731243523152164130668109255826997247$$

• 1499
  2999
  $$17537331055217019373813793980140428996762007940165414412037899012395481925281661101828540443292484630826575203397718758699647274470734979877085519459002350423944978242664548632243401355791731473268341092170069314725677729132473171262691809694657480322332526275875721167754624586680565177898054854942790337156977105108828923716313380366502376637658596066837351781686391648520996613526331666834254976000087526677764529440217091269193357761841856604274687$$

• 1511
  3023
  $$71832908002168911355141300142655197170737184522917537431707234354771893965953683873089701655726017047865652033117056035633755236232130477576542287704073627336478630881953991197668971953322932114507125113528603913116375978526610109491985652509317039400274027625986953903122942307043594968670432685845669220994978222525763271542019605981193734707849609489765792897787460192342002129003854507353108381696358509272123512587129205838615993392504244651109122047$$

• 1559
  3119
  $$20219166106969189340823874802261963994087288716463189902887380910103130677166133063558291985907075930975203628413987364067500973967655217764506695267124455367394414260443416413513980705076886369641183937926636566437721556242385383326420667703540909311244396271489154202768021223902218212914603818213480294475840097221369119946240275086051448036413550575282770883084695128310465743502306716354071234040911940787574095939788098083442389517818778243412564988620475086143487$$

• 1583
  3167
  $$339221317116501194915899765514506258513025165650465693049760613203076805647042482292059193238631968822372081917885203428231102420465728601962165959942724686581135445240939452947469373308907219230925985422325773828624005096934647931310158048926529800351158465036368181717146889965991877837202297812592293012164776092543909541067981483018103730819686003328443308184022676461812398839338796278522985572890932467572340723586547915775098992496581491445833179928123252542847905169407$$

• 1811
  3623
  $$146326217885143466722104534063154500943682173846505522523531913193340095052437255508302811033960898636991443654872959841661956079399771727454389088538554421785648329011963330511130442388448145642728007484178386213224844406411053111343233884415696965610755700253714714480465484196604750061726216688954210872086992132421878104521981255966648559553684299451731891369960892141143347354203453957171727038798983255704566803062523551689143781139213305220007510905139362754788683390487298377867377999897267606438484049002379876934153360547742361266946047$$

• 1931
  3863
  $$194500905330256161598402280849172418540938179859835119089256358565038420555153477376216652612241623073122199241498582833932449334370424257073465422810970787997670323381109141050054604586266122946266335913777708609694640144756980452747828809552809801660721978312317110409411495974207748226644382841632989147038290938703199265155184056381874486185430887929051834507484058738763143687056425283943306785327322735535269066261352030067521656466151450582338123803166302849069603104580053998151393274727096258575143034144478282747656019513679922594844320257210158998742198848119692641435647$$

計算した中で最大のもの

$p=999671$のケース。
$2p+1=1999343$が約数となりますが、$2^p-1=2^{99671}-1$は10進法で$300932$桁となったので、ここに書くのはやめておきます。

私のパソコンは、開発用等ではなくスペックはかなり低いのですが、このくらいの桁数でも2～3分で計算してくれました。

感想など

• 命題を自力で証明するのは楽しい！
• 証明した命題の具体例を計算するのは楽しい！

命題として見ていたときと、具体的な数値を当てはめてみたときで、印象が変わって感じられるのが面白かったです。

参考にした記事など

• Sophie Germain prim.ipynb
  https://gist.github.com/terasakisatoshi/028f7bad99377633cb01e8b1cec72e67

• Julia言語で入門するプログラミング(その1)
  https://muuuminsan.hatenablog.com/entry/2020/11/22/022956

アドバイスなどをくださったみなさま、ありがとうございました！