x^4+16329*y^4=z^4+16329*w^4の自明でない整数解
富田誠二氏の計算数論サイト(Computational Number Theory)の記事
http://www.maroon.dti.ne.jp/fermat/dioph121e.html
によると、Elkiesが2017年7月30日に、
x^4+16329*y^4=z^4+16329*w^4
の自明でない整数解
(x, y, z, w)=(346429732854975524407446847, 54141872796715970999006713, 606051030994671192182211305, 33186693159559232548599185)
を見つけている。
今回、Elkiesの解とは別の自明でない整数解をいくつか見つけた(これらはElkiesの解よりも大きい)。
3336967878912435316510997681334353582488640115322603572239556909865501786578321553935838297676341362485201^4+16329*933312101447740809699456856506832428924412880871520955086714173064356847648587078482182025573255921786239^4=5192028969273974407462429694682161553044792326040873907499363951717919983094723726687720732630468664969151^4+16329*921748988913798281251975156840975541631739329846749380173092868788061348867815094269700409380871380697711^4
9909815788886720560307621757511345658036899705952995384836675604420126628070745893254518600252445491379431288830816879621319214616108463776367192055107679127477013528848495244264662960448641061048295931643979692525634304102001788346899800142390206411344575620533679646457249268854523633950420508432730184368070357793157196359328531835319345644526403599754791629533115556079255925473864347017149965594675701109681075166875887^4+16329*1266085888906843406595521384286936179139929391167587724873937404534014039643589427066941576771999464162843470830300705806750793555575392073801612224743916627149846446863562973384199326836517139173322603505377146574776883324167978542828677902039634833659865573695539949108503933924552716641183131737555423898728017176995473060089222891929100823292578010711743967748169585999498530287854885068255868415200457298662535778720113^4=12325529653362262309055530041949369128280968795694335232714091649866248828203887737495171597887665394771485705632842414754372771931168123866405395183345905525485267578357015815317289688370090243444488704856228212934973932379318343935779582584570804405372432754814162196081462335473340158673717357149811451256267073038877516509535697002349137671535478948475873202672720957899039365210288198974603285103252811795967211431913713^4+16329*1149627975568698342152386900151087291104139698573752123003478640912108160489552417173711420863220439229210945971724829326302763759484268016236590903494309770858407602644957597668427401084932043222870169706871373834562744953148577046051104540140963160367991560584942600515709132694263808082113716979525842989468698068724847090117942275100691203716497338009337605391435815820284909448568966889197451093376653387623600486317713^4
17409470025300731108517522657702802307776177092971209799431290167040359997346682278993702292720912912790149348468696543607183640980195664020467558999956577233138905805375388801236814481410016075359523277641690914684078112150588191516766399930318243143609060145640037623777724934819039765147436995744528522016579094050850702204061324799348328162323319924629914483349573847285505275347670229623488926112719118743940051002339891075003180668777714195370807416243248943400628250803992708445992500928500991780261285733092132057436810098948974097789849258043992250932890708909996058092491794810700853407650868765280775151206282916677970925433632007987959750408936980258187487198743419269902268929457967462312344738300370751440111229317973950547141927055372582951370839292397922065975394391265948812272645556611532503614092040609256232844472124925378864497635226776048840359424439254281982101776690840061539984680523271415481067704456309594558610296980315299681^4+16329*1563286847667443188969480736386905400745454414486395804008128292020877879994195533138890763362597047801070168968754729998732421151581312258811097182869547227807015994845326440576272968014935313882389630233094809789970013012692925015409314894303721301417484991404907224931623523584024920360364565655739310019013981626163349717925604358804606575375988937839263272955693568126722851820281534891632125567814747652166566498402937081510339441473095643265617143273920614780811489408118727881564493447461508263272687401453639502998566122714916323627452336422531229888172136279663966414879406076206181630930870124254292028899616107553345133726273815070171230870766814503185694479283498984711216742046536012058785036976210991530560867129229459679509161238385477576699335205623636897418891201447960230421608092035172272862175866204729635810817204258658514574814156363372685964693509122459823206462048348910704858172176919652584827972104123844293480982695992610959^4=20098400649519800580581896967280608721816297171900420661673280985201327374315828167540818423550870584351261196392661822576004222292088258951288677580687597375977363302193541476479067048378865403019740445800640080496991917078500628136237779070253142528520690566177160912135332809496478933804179571644076513869550520762467710545146408594064756899374795541275094926797479364241195266124064789425345116349685549626111355959971248259400501457094019552729550377887327767028491979793572601796332783910779630836028587507570502830716974650277059125721305623235512903097669803464040645654720066296194790116198441832281011811489570606257366448086485859506782242490006411109781072096723064089683874157823639717127748207402051822406052810553961961500519558809559539622982264596243203376964454635567765313491006260531176657162751172174301496687115493546109973256150395078195929965031541384810700913326225988893957178492269879018755359366492398631100309718225712222031^4+16329*1125643776551626283094893573190901013294665664442815058233862526140089496974950355408225367467360623760041678955210548970088160160311282672010021397861472915031441501972826234665979598953914013777827537925854356022943791915219511604062064245631178083494145429132216063425984351093414248296378010243808681833957445085453658623159479435911822161675486678805917170492211948828967138956113024910224064669151683230004738459228420102886981346843209714093125818370158208847052239581461165468775789534817130792494614373024731270281598428613168704304004028768989422276606958274380621147348865409287755077616702942745944631383671582026050388926580036448651261210302616348407890418696145835070388486319136242756618432125470079435380714106758551273868470515801479094912090098221644413570169042853856270796752611884471880686483265360315628031826164362072594183701011938774403640913593008068895605087486799921712335639569687950689463689931965192248218438549404311391^4
....
Elkiesが2017年7月30日に発見したn=16329のときの自明でない整数解
346429732854975524407446847^4+16329*54141872796715970999006713^4=606051030994671192182211305^4+16329*33186693159559232548599185^4
よりも小さい自明でない整数解(先頭の解：最小解であるかどうかは不明)を見つけた。
655700933372^4+16329*194394472427^4=2153477294662^4+16329*105160799831^4
437464581025644405995498027645111564922860755583^4+16329*33959339400227450135648500462588483336404118001^4=471772341403250876373595796473385083450472327653^4+16329*27097787324706156060028946696933779630881803587^4
16161609772709337127791960690668236810622849095052965806078112563970299568062248610002975004411382313079832^4+16329*6413893634014646142573923642938779779091138831019712261791104737310899704325496259656328502494509199554811^4=69077147190410722019485347287968223304768397789349002117914977587176720453096113119931714170373558535723842^4+16329*4169213849525630835764753676521217519737970907839495000576268267330384472681276642329419330697926044973991^4
3999299785824298395746452294541278155684774702407877633049981790127598524485865904159168808705178281231752999898870650751285764760978078206400522420239260759975754627541524610304865721038831^4+16329*1036904751770016178781157840550825382425999572069065471268866256092205142718260001334008698371267989898272280451127873322458794138835084562420002458953602241067032698589485271267138899234171^4=6278238705024331921400509817935512097932150899442043783641917320727987082863156401840758050252975764959241750578164452708126767548235571696723121127942432928437147405569986802624861589935239^4+16329*1018602946399709884648234581944532668297385548300918812069513566078911978751544459865976673420362819339926669644279147369423712323007645418204726250682736496615547708032817011318806562960643^4
....
最小解は
2187137^4 + 16329 * 163892^4 = 2415743^4 + 16329 * 78084^4
でした。
# 探索プログラムを何度も改良し、かなり高速化できました。
# 3000000までなら（14年前の遅いPCで）数時間で終わります。
# このプログラムで「100000まで」にすると、定数によりますが十数秒で終わります。
＞らすかるさん
x^4+16329*y^4=z^4+16329*w^4の自明でない最小解を、(14年前のPCで)わずか数時間で特定するとは、驚きました。n=16329のときの最小解をらすかるさん(英語ではどう表記する？)がBrute-force-searchで特定したことをElkiesやSeiji Tomitaに報告しても良いでしょうか？(直接、自分自身で報告しますか？)
らすかるさんのこの素晴らしいBrute-force-searchプログラムの高速化・効率化のノウハウ(多重ループの構成、primitiveな整数解に制限する方法、mod pによる絞り込みを使うか、平方数・４乗数かどうかの判定方法、整数の平方根・４乗根の計算方法、演算は128bit固定長かどうか、整数の平方数・４乗数の表を使うかどうかなど)を可能な範囲で教えていだけないでしょうか？
らすかるさんのn=16329のときの最小解(先頭行)を使って、大きい整数解を計算しました。
2187137^4+16329*163892^4=2415743^4+16329*78084^4
491354218601741881832999663930146417367034571^4+16329*40652239146504168353565861842514770292760692^4=566164607296900855045109796799540398328779061^4+16329*9565408169771193199533896849798062948776796^4
27362207959873289612821603288256718930165496231118069449040647298772982990936688010140183061599487813835508727003033398899^4+16329*1738558521432562494802098742425351406211155307287554800170682914627271449561174123346305729405515693993998858054854788972^4=28458896630578874726526804761466998750712595986971770245786391099819360804018392347267138734357334509764005771591164480909^4+16329*1347068032714485019474788363299943855160381865947735915999025832019066318642619853909160205058044856103543041712397501636^4
311720480619907860336573604399912281083304226202966414379475371968878185767143324793919160323043321486084084769504312461409494429742724892065382678780941540296632870146177791393747120880602655928373051948157619013175068966491278916580393^4+16329*26746460695613543701617802144562813067915060577418955948973051919659284284646528804241267523815781493423152742264483832166807983982562903066816092557557318899575433015278545203245151791494664100714708784322353055620003484740361001536492^4=365254476380840936872179357773375058815039107701917453016194091596808343397965681870819602797182638471614096319268232671500890922964642800316742485563040877486654447457888267318785033027557657457375914956213322309825538824439384754669527^4+16329*493009111823349647059465379616036647979089980704455345821068699950246966543776002303960331727853495761521777493834511457828689065165587777401973634620994491280601596017619226132073705621975233137679218632744589968271459938201530765084^4
....
報告は構いません。ご自由に行って下さい。
これから外出しますので、探索方法については帰宅後書き込みます。
名前は数学系サイトでは本名を出していますので「T.Suzuki」でいいです。
x^4+C*y^4=z^4+C*w^4, 0＜x＜z≦N, 0＜w＜y≦N の解の探索で採用している方法は、
大きく分けると以下の2ステップです。
[1] (z^4-x^4)/Cの値の収集
[2] y^4-w^4の値を[1]で収集したデータから検索
[1]の内容
基本的な考え方は
> 1≦x＜z≦Nを満たすすべてのx,zについてz^4-x^4がCで割り切れるかどうか
> 調べて、割り切れたら(z^4-x^4)/Cの値をバッファにためる
ですが、このようにすると時間がかかり、また結果の値が多すぎて
メモリが足りなくなりますので、両方を解決します。
(高速化)
まずn=0～N-1に対してn^4をCで割った余りを計算し、その余りでnを分類します。
例えばC=16329のときは
余り0: 0
余り1: 1,5444,10885,16328
余り2: なし
余り3: なし
余り4: 557, 4886, 11443, 15772
余り5: なし
余り6: 6216, 10113
・・・
余り16325: なし
余り16326: 2067,14262
余り16327: 398,5045,11284,15931
余り16328: なし
のようになります。もちろんこの処理は一瞬で終わります。
そして余りが同じグループ内の各値についてkCを加算したものすべての
組合せの値を計算してバッファにためます。
例えばC=16329,N=3000000で余り4の行では
557, 557+16329, 557+16329*2, 557+16329*3, …, 557+16329*183,
4886, 4886+16329, 4886+16329*2, 4886+16329*3, …, 4886+16329*183,
11443, 11443+16329, 11443+16329*2, 11443+16329*3, …, 11443+16329*183,
15772, 15772+16329, 15772+16329*2, 15772+16329*3, …, 15772+16329*182
のすべてをx,z（x＜z）に当てはめて(z^4-x^4)/Cを計算します。
（必ずCで割り切れますので割り切れるかどうかの確認は不要です。）
C=16329,N=3000000の場合はこの計算回数は約9億回となります。
この工夫をせずに単純にxとzのループにすると4.5兆回ですから、
回数は大幅に減っています。
(結果の絞り込みによるメモリ消費量と[2]の計算時間の削減)
「(z^4-x^4)/Cが4乗数の差に絶対にならないことが明らかなもの」を無視します。
具体的には、0≦m,n＜1360に対してm^4-n^4を1360で割った非負の余り(0～1359)
を求め、1360で割った余りが出現するかどうかをあらかじめ計算しておきます。
そして(z^4-x^4)/Cを1360で割った余りが出現しない値のとき、その値を無視します。
C=16329,N=3000000の場合はこれにより残る数は約2.54億個となり、元の個数
9億個の27.7%に削減できています。
※1360という数字は、いろいろな値で実験して「これ以上大きくても
意味がなさそう」と判断して決めた値です。
※(z^4-x^4)/Cの値は128ビット変数で保持しますので、
C=16329,N=3000000の場合は約4GB使用します。N^2に比例しますので
N=10000000とかは単純には処理できません。
上記の処理により、[1]の実行時間はC=16329,N=3000000で
(私の古いPCで)約80秒でした。
[2]の内容
y^4-w^4の値は比較的単純に全パターン発生させています。
ただし、y=2～Nに対してwはN-1から減らしていき、
y^4-w^4＞N^4/Cとなったところでwのループから抜けます。
これにより、C=16329,N=3000000のケースではy=2～26万までは
徐々に遅くなっていきますが、それ以降は計算量が減っていきますので
加速します。例えばy=3000000のときwは2999999～2999954で終わりです。
「＞N^4/C」でなく「＞[1]の最大値」の方が正しいですが、値的に
誤差なのと、定数より変数の方が遅い可能性を考えて「＞N^4/C」のように
定数との比較にしています。
さて、発生はこれでよいのですが、それぞれの値を[1]で生成された
膨大なテーブルから検索するのは、単純検索では時間がかかりすぎて
現実的ではありません。
「ソートしておいて二分探索」も考えましたが、もう少し早くするため
「9999991で割った余りで分類(ソート)してインデックスを作っておき、
探す値を9999991で割った余りにより狭い範囲を探索することにしました。
メモリの遠い場所を飛び飛びでアクセスするより連続したメモリを
アクセスした方が速いと思いますので、おそらく二分探索より速いのでは
ないかと思います（これは予想であり実験はしていません）。
9999991という値は、インデックスが余りにも大きくなりすぎないように
適当に決めた素数ですが、Nが大きいときはもう少し大きくした方が
良いかも知れません。
もし、他に簡単に高速化できそうな箇所があれば教えて下さい。
>らすかるさん
とても、参考になりました。
短時間で、これらの高速化・効率化を全て実装したプログラミング技術はもはや芸術(Art)です。
ありがとうございます。
