8

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

493
0
$$$$

経緯

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

ソフィー・ジェルマン素数$p$$p\equiv 3\pmod{4}$を満たすとき、$2p+1$はメルセンヌ数$2^p-1$の約数となる。

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

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

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

例えば

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

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

といった感じです。

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

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

Julia

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

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

計算結果

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

※大きな$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分で計算してくれました。

感想など

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

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

参考にした記事など

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

投稿日:20201125

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

みぽ
みぽ
156
28138
今日もねこがかわいい。

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中