x^4+9719*y^4=z^4+9719*w^4 の自明でない整数解
Seiji Tomita氏の計算数論サイト(Computational Number Theory)の記事
http://www.maroon.dti.ne.jp/fermat/dioph121e.html
によると、Elkiesが2017年7月30日に、
x^4+9719*y^4=z^4+9719*w^4
の自明でない整数解
(x, y, z, w)=(195094869572512833, 14377568349438717, 62388694687774103, 20884354073695547)
を見つけている。
今回、Elkiesの解とは別の自明でない整数解をいくつか見つけた(これらはElkiesの解よりも大きい)。
43938199578841830692004472163077033372043357555372513598159259067041701868054776^4+9719*11229230674136694938483221750090350187124728256135514895615355543533109838039641^4=102665194434130650715391733334846582615695797955527827329831284570599048328403858^4+9719*8346434277626245069312531973832832894092751877249589681608652957652672315410053^4
273776412190928217271701875886049501379163401840129400262352420851181467160656207392603532326250833154017553138612261559049420103945521275196943117681879787135990499267831353508038848287914567341847820023633771711455666918027042595078589402083968735768196503411812465725309476358121129250654019211613330799041130837258638383^4+9719*30745066646714798806980233199117780334438820042812102197970980349715361708940636334646329699820120790616652128606404409474904653882741313366589357983275056098929075373779221084223292113261131104333847984769800128921651408630426099933056731969761325441137021628659339844589614530209731827311359411084400046632945964576196939^4=345696273966939622870776734745261911712979465117798722935524198331833750644831859037278016208072864884772384568910408922387517030968220942909558897460339811832767363189987870971442815776300244975210133025792566994665279213643912898895791447048707138074717636952695771083459927441538515789831204767580149623869316663236473773^4+9719*6771779388044330273955280246046976889833465616922327973580387856164600547548752453088168405879443547031708318507021955028872344875174757462384098057121714533336787399727048596421969617132571893213076984050201701185113976758135998660656050314848524672296643781698238058539464169070602980918964225762127105023550689250251809^4
150239881604780907653843047363432621910624218870975039404713013477658476209143065642121946424940468898580173047650819124729915614559440872778439585949783781606229772791967186671348576208914989776229068526898770631191171685503621650119123782011756991888461178262400883865677559286767278109974299326384179656264771542817215914933028548274873967726249863671234854903917437586126100168062235430554150145116448057432622863829796371886937015218839313577482056645335418924535730621613934538725339490683064654422582867260784334620584238068599192163329215814194352959596025317860323809214135498446503720133685517900788998087472580582745703337423684374619006334811427207241343297133274048915439561279837093931030929955786390744657435132^4+9719*19989242742409064452304530214859567882301839657411524281175897228195581581774483419477629664381569376411610574939077251786733984903034944031527631600882597821176427371122019639813969258005764262822876651451259753400362643888446586149318032239059650177053382502336172141499755193454096816593872944763413234170317943247976599377160490738770952648940673135255430671021018850624603444577622564793077663851870529053846948847487574346039227843066350476457781704350540885651314852258870306925642394463515635616131090226231452171413073761878502257043869715470059988794456676176270303077695986887157104396216926165366248056025706065645850570070231288583201051750851451650813266509482167925309082630945047972397650630317620841902369607^4=213073408533071200466438315679773859414037807389330406818425944940464746289411415759600423275067155462507333312133791023994830768116108555334518766845202411349358166562379974987923855129643518502269669208905312598652867296660004396539147623289457335634838420884610386075487310262712357936634051223892005037707052117560085992718996827316408549947643071070429428920436944417231817118707380140998051362007420229419032234485566431316560940994846053710995668809402455898522520635456012527534416757937244295240396119508041746046727462100697343451561233302750700107761671663720402579847661487766317836330641755751991035547189175375609821259826478937420536944736536495515915593870655150117897137191098566545649906966649886592024687586^4+9719*955266233687699818560559223920844618836023182040264856728413259406508444981633286348529285660659478230776179888580047968237732949187616820498762030923612093199703885682243132377790382237078645857323575884254235753535893163680995990689914853507131071739031705066995261770161798527596458959377687739195226310442248332980093218162268941740574758190395997809427334485483426410635538970759005354889408445120194941622841371102445463835414082269229568046755683671804772344281819021822356010716694621210911323139993856187684970634667582154214839033469447382055727260758772443755953800146009552780934336101819785034431097213158865308855404064033565683975818224184977774044165736311532475510109339475442899142008373303544440553381211^4
....
もう少し小さい自明でない整数解(Elkiesの解より大きい)も見つけた。
219903949140396512236362361858828356^4+9719*14513986665994122439174472171533629^4=229336846750635711203552439045328694^4+9719*4351808554484275495205682201467047^4
33595129708494551806013881971116396357402304099765925669816700115825158554085150647628229724967268169347760186451785912302894151674422369007^4+9719*2150855528188626413735718196927796034122504489335318578564297348415275179038498890262650315744271281307249793772252411770670926960928205161^4=34887754680067931683265474897888192125519382540722695870719146415610415790895367799361939442230180750890985443639593784607382340089588871461^4+9719*434394414958133340767467656615795502111652392578221823240595251155239294581935413204769118781553881779200720603363332838305449869404799747^4
27694214951494692566190846120426314807864789961954872222762575135737365233347741327531701031592267881697812722391147050729892040626296267663546245324954723422455874694138599203175258569454547317216890280481933134167643927770979358615791026631739900663110075942517764251454333931958564094980097762756498452722936^4+9719*35201107622302772226809783318238981375374682311784177479206924016149916012457366567271738830550797782715254020325913883581252199002833989640771337243989051191337400825231901744901846695069171655427602654515295065337949775590164614938124403638437523977779568654398830155298900585794458908425800315413037301932941^4=62890881484811194217671033362210347883355855875575035139997705034912144428878339305873820141095999152373278321296391001511033812482895350196158795121824649768715500132188680767232548616923351936499204138514607304984247650512112522366370814064143149478186099682217597605233825476224034810043656222301394182579178^4+9719*35192225444330231076150591165329084775607449515456148355263335782199642378603829389412499388456664758635677177484574017981031344710364175424453762349750801501181850050868261383212733399868437583137025061550053276295257669892101712563035171226368973652372478825000836552260082502736482521701316603676754157779543^4
....
別の自明でない整数解(Elkiesの解よりも大きい)を見つけた。
3731738952351029597617787188439281091238499256318797^4+9719*133709279078051674371527648441931890546563834925230^4=3745861851349052004196125211263585323437186419248703^4+9719*63094784087939641479837534320410729553128020275700^4
1507943293835051268119298410144596627523341867566834192392779356416739941452441559104620435861848509845802374348347096794808363702660567870499835280794551956521928362617793076191796615705430948264497808107^4+9719*184089047467184011444301471270731894622763159518780035376103173799250423286441752311833439549773150067294972694352434676079661840061204459982442751395288357473150882211001464273171267678013804749501123385^4=1580661270853855478336311736619236446947497372740459773297663701849139177054577273593166547587983579546169166219176956402618073497312163744682177331828127514607593780730480386339876084656314380328365529393^4+9719*179500837626837039640765161102467202498014366349347869148318553362745754724236820130897119080902198434538986659796863362968887133196774910929267503772589432955176208352435086467226077076403355569837483045^4
5619925937637579992258205613016709687713194937507301937051474834160052809300773756698801200957847289583313064131514756870034397548427546306096019724928936042853609298153146324380607373787790785940925491849003369821854934654711916364317427107620816357605329648458714456991554300083441186127854657483608577976819458944072253619180796157246306874848708252471964430433614206487473113287990534940731514735103627817739848122066016418640221106705259815572394701647^4+9719*257633533436728963949448893769683469708238274131471080450373908989379921496818668919229189992232464793991424395573707725996743280049023184489457707726857691658214722475780322961499124534666218972867424853094392150680920554949916345044089234220247157819630353519222512305592845897326263743604590356232627499280561933876448459392811123745351316979791216508781373734411477502866345536512039153144571593242072903356642743654402272565023181879752111494598174160^4=5679256642055848995841675261263614816971316838005678871408280186486973687113141509124701651438450506531940677430962529722587000708368048121784655491387660351914752137324268765919852037994883049743524515556039754272388517290344888348819114522642906666377329165529508260116511825044531434407204924852970961316926296512179958694415115488400003666024683181235252928530610726470442105827526229850773692894711736457772310596838289859680318950124601754466888985853^4+9719*39019988654616053967899347464842176582371228360413591333652852645224467565020093210273062410783619949146642101665156536766272519653485893953721124566763853647499473379831884734724196500795100040127693682087530101986992623214943577464347840890204386040367231834746503319194778908124977653146746490579289201253625906662076916778785532023132638900083427307661116750571122411978617161166435397066319204798470296805669630206964932635466035216957582977873246870^4
....
9719の最小解は
4387435^4 + 9719 * 223114^4 = 4456855^4 + 9719 * 51748^4
でした。少し値が大きかったため時間がかかりました。
あと、20000～20020の最小解を求めてみました。
もしこれより小さい解などご存知でしたら教えて下さい。
74^4 + 20000 * 35^4 = 282^4 + 20000 * 33^4
36^4 + 20001 * 197^4 = 2337^4 + 20001 * 62^4
546^4 + 20002 * 229^4 = 2666^4 + 20002 * 123^4
73^4 + 20003 * 7^4 = 93^4 + 20003 * 3^4
94227^4 + 20004 * 4178^4 = 95811^4 + 20004 * 2396^4
19789^4 + 20005 * 2904^4 = 33873^4 + 20005 * 1898^4
89^4 + 20006 * 68^4 = 551^4 + 20006 * 64^4
732^4 + 20007 * 199^4 = 2346^4 + 20007 * 91^4
502^4 + 20008 * 83^4 = 746^4 + 20008 * 77^4
887^4 + 20009 * 119^4 = 1467^4 + 20009 * 3^4
379^4 + 20010 * 40^4 = 517^4 + 20010 * 12^4
48159^4 + 20011 * 9898^4 = 88181^4 + 20011 * 9096^4
685243^4 + 20012 * 110194^4 = 765627^4 + 20012 * 109026^4
10697^4 + 20013 * 724^4 = 11677^4 + 20013 * 46^4
19932^4 + 20014 * 769^4 = 20096^4 + 20014 * 543^4
134542^4 + 20015 * 6671^4 = 137662^4 + 20015 * 4495^4
714^4 + 20016 * 73^4 = 954^4 + 20016 * 1^4
269^4 + 20017 * 176^4 = 2086^4 + 20017 * 61^4
133577^4 + 20018 * 11323^4 = 152033^4 + 20018 * 8671^4
197^4 + 20019 * 48^4 = 367^4 + 20019 * 46^4
2474^4 + 20020 * 353^4 = 3818^4 + 20020 * 287^4
>らすかるさん
n=9719と20000<=n<=20020についての最小解を特定していただき、ありがとうございます。
n=9719の最小解については、ElkiesとSeiji Tomitaに報告したいのですが、全域検索の範囲は、
max{|x|,|y|,|z|,|w|}<=4500000 (驚異的!)
なのでしょうか？
はい、そうです。ただし、実際の処理としては
(1) 0≦x,y,z,w＜3000000
(2) 0≦x,y,w＜3500000, 3000000≦z＜3500000
(3) 0≦x,y,w＜4000000, 3500000≦z＜4000000
(4) 0≦x,y,w＜4500000, 4000000≦z＜4500000
に分けています。
と書いていて今気づいたのですが、もしかしてこれってまずいですかね。
ひょっとしてz＜3000000かつy≧3000000なんてことがあり得るでしょうか。
もしあり得るなら、全域検索になっていないので
追加調査する必要がありますね。
再度調査します。すみません、もう少しお待ちください。
※9719以外はこのような分け方はしていませんので、全域検索になっています。
あらためてmax{x,y,z,w}<4500000の全域調査を行いました。
最小解は、やはり上に書いたものでした。
（というか、上記の範囲に条件を満たすものが一つしかありません）
今回は速めのPC3台の分散処理で10時間半でした。
＞らすかるさん
max{x,y,z,w}<4500000の全域調査(結果は同じ)をしていただき、ありがとうございます。
毎回、らすかるさんの手を借りるのも申し訳ないので、らすかるさんのアルゴリズムをGoogle AIモードに読み込ませて、いくつかの指示を与えて、Cプログラムのひな型を作成させ、
それを自分で修正して、なんとか完成させました。
動作確認として、n=2049, max{x,y,z,w}<=10000で実行すると、
x = 2476, y = 549, z = 3842, w = 231
x = 4952, y = 1098, z = 7684, w = 462
の２個の整数解を0.5[s]ほどで計算できました。
このCプログラムを自分で使用するのは問題ないと思いますが、らすかるさんのアルゴリズムに基づくこと(およびスレッド3242のURL)を明記した上で、GPLv3を付けて公開しても良いでしょうか？
問題がなければ、もう少し修正した後、この掲示板で(他の方も利用できるように)公開したいと考えています。
Seiji Tomitaの計算数論サイト(Computational Number Theory)
http://www.maroon.dti.ne.jp/fermat/
のNo.202～206, 212～228 ( 1000<=n<=20000)を見ていたら、暫定最小解の大きさが300万以下でも、最小解が確定していないもの(???付き)が思ったよりも多いことに気が付きました。もちろん、巨大整数解(当然???付き)もそれなりに残っています。
H.Nakao版のCプログラムの公開後に、皆様(アマチュア数学者)の協力があれば、これらの???付きの大部分を(比較的短期間で)確定させることが可能なのではないでしょうか？
結果が出たら、この掲示板にログ付きで、投稿していただき、後で、h・最小解・発見者・発見日・検索範囲をまとめたものをSeiji Tomitaに報告するというのは、どうでしょうか？
> x = 2476, y = 549, z = 3842, w = 231
> x = 4952, y = 1098, z = 7684, w = 462
> の２個の整数解を0.5[s]ほどで計算できました。
最後に最大公約数が1でないものを除外した方がいいですね。
> このCプログラムを自分で使用するのは問題ないと思いますが、らすかるさんのアルゴリズムに
> 基づくこと(およびスレッド3242のURL)を明記した上で、GPLv3を付けて公開しても良いでしょうか？
はい、大丈夫です。
> のNo.202～206, 212～228 ( 1000<=n<=20000)を見ていたら、暫定最小解の大きさが300万以下でも、最小解が確定していない
> もの(???付き)が思ったよりも多いことに気が付きました。もちろん、巨大整数解(当然???付き)もそれなりに残っています。
そうですね。8桁以上の値になっているものはおそらくすべて最小でないと思います。
「???」付きも含め、100個ほど最小解を得ました。
「???」付きで既に最小解だったもの:
3086,3334,3628,3980,4099,4231,4684,4870,4999
最小解ではなかったもの(「???」付き・なしを含む)の最小解
1198 134247 35951 177233 32517
2572 271169 56253 308817 54121
3193 10091 20609 102997 19519
3622 347731 114284 565013 110014
3644 43639 15809 118519 9823
3646 95033 11191 105497 7993
3742 250139 172316 322387 172226
3814 6661 12661 96317 7481
3818 39021 8373 67219 3637
3868 137788 10327 141656 4633
4006 22063 67241 142183 67157
4051 11973 137465 368461 137025
4054 239933 53137 406147 37967
4252 350094 66949 422378 63381
4358 91496 95921 100212 95919
4406 60271 53068 355473 45564
4414 92198 11873 110846 6721
4418 112753 65441 337601 62681
4478 249983 32590 303719 17780
4519 16057 23369 155665 20255
4574 56333 26627 218107 10033
4630 63483 88381 489443 83505
4955 36819 35946 246607 31000
5062 27703 26929 164377 24857
5462 108077 89519 763517 37721
5479 8022 15397 29938 15387
5606 10161 7620 51505 6784
5686 141304 50477 436976 19667
5721 14831 8176 69077 4722
5758 294 6761 57874 3447
5788 85784 5533 87856 157
5816 142534 30999 241406 25311
6067 149423 37373 202463 36403
6263 122764 53411 140282 53369
6428 433315 71881 674365 9217
6606 14504 8771 79096 579
6718 14591 33742 287719 22924
6818 824 15619 28096 15613
6823 974078 126665 990946 125495
6827 186347 49724 277889 48242
6871 186299 24782 212219 22522
7197 87523 9096 101917 1664
7338 60167 15859 147743 3249
7482 26203 2801 31019 953
7495 31157 4371 43793 393
7606 29577 31856 297481 4164
7646 341709 32637 384661 15271
7727 190722 26691 257444 18223
7822 404162 101011 956866 24211
7845 26708 4427 40306 3257
7862 729099 113466 1098613 63646
7898 100351 67936 362041 66142
8222 19764 15639 134872 11831
8447 925973 356513 1151989 355841
8498 14057 13582 130409 154
8549 132233 56488 534589 28546
8678 110279 32519 275161 26249
8712 30668 6907 56056 5939
9066 20190 15587 128982 12995
9069 47924 21509 186982 16809
9186 136624 33111 326468 7561
9463 287148 40385 362852 35265
9539 565663 228946 1704619 208036
9641 11587 7085 65541 4965
9719 4387435 223114 4456855 51748
9803 154887 8865 158809 385
9813 78019 6429 85531 2347
9995 380246 47347 516178 10957
11409 65579 22978 236714 8489
12797 68089 22874 187851 20544
14113 66698 7137 80811 5588
14434 308961 32114 393503 13554
14470 209527 45102 265089 44524
15115 143123 11878 161261 7354
15285 116773 5446 118811 1678
15463 181052 25083 220986 23617
15472 146927 22043 251477 9374
15684 221566 26317 315670 3875
15748 150318 54847 592378 33519
15919 197707 8889 200268 5852
15962 47462 12803 143234 5347
16282 147683 12354 170979 2126
16313 120629 10442 141391 4384
16329 2187137 163892 2415743 78084
16602 60773 4372 66307 2182
16689 10453 7338 82772 3059
16802 33456 1329 33752 817
17283 16847 23231 264619 9323
17335 175214 10011 182148 5497
17461 562801 86065 799157 78125
17517 124341 20815 194409 18605
17565 36623 25953 228023 23401
18146 288901 133123 1545533 9383
18436 5818 10587 123234 2699
18455 40248 3833 48336 2809
18570 8546 26219 201674 24885
18952 2326 9223 106562 4559
19076 200114 109879 238266 109863
19091 38183 2312 40427 2
19235 83673 73521 853073 36041
19274 101749 11948 148813 4718
19284 1154792 130939 1373344 119173
19331 31037 2240 34391 950
19353 113786 22149 260372 10433
19365 99148 15043 125486 14433
19369 248406 32869 266256 32417
19613 78443 28018 196139 27142
19914 20703 23642 279585 8650
> H.Nakao版のCプログラムの公開後に、皆様(アマチュア数学者)の協力があれば、これらの
> ???付きの大部分を(比較的短期間で)確定させることが可能なのではないでしょうか？
???付きは今こちらで順に解決していますが、残り47個なので比較的早く終わりそうです。
（ただし残りは300000以下の解がないものなので多少はかかります）
???付きで今現在の未解決（いずれも300000以上）は
9562, 10463, 11354, 12527, 13178, 15117, 15234, 15427, 15727, 15815,
16063, 17026, 17133, 17167, 17230, 17315, 17386, 17405, 17481, 17495,
17529, 17773, 17791, 17801, 17903, 17977, 17994, 18074, 18141, 18311,
18372, 18453, 18471, 18498, 18898, 19002, 19077, 19085, 19117, 19219,
19290, 19297, 19321, 19531, 19661, 19834, 19977
らすかるさんのアルゴリズムに基づいて作成したDiophantine Equation
x^4+n*y^4=z^4+n*w^4
の自明でない整数解(0<x<z, 0<w<y, gcd(x,y,z,w)=1)をbrute-force-searchするCプログラムを公開します。
らすかるさんのオリジナルには到底及びませんが、それなりの実用性はあります。
これまで、gp2c-runで数日掛かっていたmax{x,y,z,w}<=100000程度の検索であれば、なんと１分も掛からずに終了します。
[コンパイル方法]
-bash-3.1$ gcc -O2 dqde4.c -o dqde4
[実行例(n=20001, max(x,y,z,w)<=100000のとき)]
-bash-3.1$ time ./dqde4 20001 -m 100000
--- Diophantine Equation A^4 + h*B^4 = C^4 + h*D^4 Search Started ---
Settings: h = 20001, N = 100000, FILTER_MOD = 1360, HASH_MOD = 9999991, Verbose = OFF
[2/4] Computing and filtering (z^4 - x^4) / C...
Total nodes collected after filter: 1785908
[3/4] Creating hash index table...
[4/4] Generating y^4 - w^4 and performing main search...
36^4+20001*197^4=2337^4+20001*62^4
5072^4+20001*769^4=8557^4+20001*582^4
49187^4+20001*3466^4=52234^4+20001*2837^4
34522^4+20001*5175^4=63005^4+20001*772^4
27208^4+20001*6149^4=49982^4+20001*5817^4
37099^4+20001*6267^4=75449^4+20001*2033^4
16604^4+20001*6439^4=76607^4+20001*956^4
Found 7 solutions.
Search finished successfully.
real 0m10.859s
user 0m10.646s
sys 0m0.210s
[Cプログラム"dqde4.c"のソースコード(H.Nakao版),GPLv3]
/*
Brute-force-search Integer Solutions for Diagonal Quarti Diophantine Equation x^4+h*h^4=z^4+w*w^4
dqde4.c : for positive integers h,nmax (1<h, nmax<=5000000)
search positive integers x,y,z,w such that
x^4*h*y^4=z^4+h*w^4,
0<x<z, 0<w<y,
gcd(x,y,z,w)=1,
output x,y,z,w
Usage: de4 h -m nmax -f filter_num -h hash_num
h : parameter with h>1
-m nmax : max{x,y,z,w}<=nmax (default 3000000)
-f filter_num : integer F making table {x^4-y^4 (mod F)} (default 1360=2^4*5*17)
-h hash_num : integer H making hash table of {(w^4-y^4)/h} (default 9999991)
To Build:
gcc -O2 dqde4.c -o dqde4
Copyright (C) 2026 Hisayasu Nakao <khf12033@nifty.com>
*Acknowledgments*
The algorithm for this program is based on an idea by T. Suzuki.
Please refer to the following URL for details:
https://bbs1.rocketbbs.com/shochandas/posts/3242
*GPLv3*
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see <https://www.gnu.org/licenses/>.
*/
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include <string.h>
typedef __int128 int128;
typedef long long int int64;
inline int64 igcd(int64, int64); /* gcd(x,y) */
/* return gcd(a,b) */
inline int64 igcd(int64 a, int64 b)
{
int64 u;
if(a>b){ /*swap a,b*/
u=b;
b=a;
a=u;
}
/* a <= b*/
while(a>0LLU){
u=b%a;
b=a;
a=u;
}
return b;
}
/* Function to print 128-bit integers */
void print128(int128 n) {
if (n == 0) { printf("0"); return; }
char buf[50]; int idx = 0;
while (n > 0) { buf[idx++] = (char)('0' + (n % 10)); n /= 10; }
for (int i = idx - 1; i >= 0; i--) putchar(buf[i]);
}
/* Structure to store candidates from step 1 */
typedef struct {
int128 val;
long long x;
long long z;
} SolutionNode;
/* Structure for hash bucketing */
typedef struct {
uint32_t count;
uint32_t offset;
} HashBucket;
/* Comparison function for qsort */
int compare_nodes(const void *a, const void *b) {
int128 va = ((SolutionNode*)a)->val;
int128 vb = ((SolutionNode*)b)->val;
if (va < vb) return -1;
if (va > vb) return 1;
return 0;
}
/* Function to print usage instructions */
void print_usage(const char *prog_name) {
fprintf(stderr, "Usage: %s C_VAL [-m N_VAL] [-f FILTER_MOD] [-h HASH_MOD] [-v]\n", prog_name);
fprintf(stderr, "Defaults: N_VAL=3000000, FILTER_MOD=1360, HASH_MOD=9999991, Verbose=OFF\n");
}
int main(int argc, char *argv[]) {
/* Initialize default values */
long long c_val = 0;
long long n_val = 3000000;
int filter_mod = 1360;
int hash_mod = 9999991;
bool verbose = false;
int nsol = 0;
if (argc < 2) {
fprintf(stderr, "Error: Arguments missing.\n");
print_usage(argv[0]);
return 1;
}
/* Custom Argument Parser (Pure ASCII & Safe character checks) */
for (int i = 1; i < argc; i++) {
if (strcmp(argv[i], "-m") == 0) {
if (i + 1 < argc) {
n_val = atoll(argv[++i]);
} else {
fprintf(stderr, "Error: -m requires an argument.\n");
return 1;
}
} else if (strcmp(argv[i], "-f") == 0) {
if (i + 1 < argc) {
filter_mod = atoi(argv[++i]);
} else {
fprintf(stderr, "Error: -f requires an argument.\n");
return 1;
}
} else if (strcmp(argv[i], "-h") == 0) {
if (i + 1 < argc) {
hash_mod = atoi(argv[++i]);
} else {
fprintf(stderr, "Error: -h requires an argument.\n");
return 1;
}
} else if (strcmp(argv[i], "-v") == 0) {
verbose = true;
} else {
/* Check if the argument does NOT start with '-' character */
if (argv[i][0] != '-') {
c_val = atoll(argv[i]);
} else {
fprintf(stderr, "Error: Unknown option %s\n", argv[i]);
print_usage(argv[0]);
return 1;
}
}
}
/* Check if required C_VAL was successfully retrieved */
if (c_val <= 0) {
fprintf(stderr, "Error: Valid C_VAL is required.\n");
print_usage(argv[0]);
return 1;
}
printf("--- Diophantine Equation A^4 + h*B^4 = C^4 + h*D^4 Search Started ---\n");
printf("Settings: h = %lld, N = %lld, FILTER_MOD = %d, HASH_MOD = %d, Verbose = %s\n",
c_val, n_val, filter_mod, hash_mod, verbose ? "ON" : "OFF");
// ==========================================
// 0. Precompute Modulo Filter
// ==========================================
if (verbose) printf("[0/4] Precomputing modulo filter table...\n");
uint8_t *filter_table = (uint8_t*)calloc(filter_mod, sizeof(uint8_t));
int128 *pow4_filter = (int128*)malloc(filter_mod * sizeof(int128));
for (int i = 0; i < filter_mod; i++) {
int128 i2 = (int128)i * i;
pow4_filter[i] = (i2 * i2) % filter_mod;
}
for (int m = 0; m < filter_mod; m++) {
for (int n = 0; n < filter_mod; n++) {
int rem = (int)((pow4_filter[m] - pow4_filter[n] + filter_mod) % filter_mod);
filter_table[rem] = 1;
}
}
free(pow4_filter);
// ==========================================
// 1. Grouping by Modulo h
// ==========================================
if (verbose) printf("[1/4] Grouping integers by modulo h...\n");
int *rem_counts = (int*)calloc(c_val, sizeof(int));
for (long long i = 1; i <= n_val; i++) {
int128 i2 = i * i;
int rem = (int)((i2 * i2) % c_val);
rem_counts[rem]++;
}
long long **groups = (long long**)malloc(c_val * sizeof(long long*));
int *rem_idx = (int*)calloc(c_val, sizeof(int));
for (int i = 0; i < c_val; i++) {
if (rem_counts[i] > 0) {
groups[i] = (long long*)malloc(rem_counts[i] * sizeof(long long));
} else {
groups[i] = NULL;
}
}
for (long long i = 1; i <= n_val; i++) {
int128 i2 = i * i;
int rem = (int)((i2 * i2) % c_val);
groups[rem][rem_idx[rem]++] = i;
}
if (verbose) printf("[1/4] Caching 4th powers up to N...\n");
int128 *pow4 = (int128*)malloc((n_val + 1) * sizeof(int128));
for (long long i = 0; i <= n_val; i++) {
int128 i2 = i * i;
pow4[i] = i2 * i2;
}
// ==========================================
// 2. Compute (z^4 - x^4) / h with Filter
// ==========================================
printf("[2/4] Computing and filtering (z^4 - x^4) / h...\n");
long long count = 0;
long long capacity = (n_val < 500000) ? 5000000 : 300000000;
SolutionNode *all_nodes = (SolutionNode*)malloc(capacity * sizeof(SolutionNode));
for (int r = 0; r < c_val; r++) {
if (verbose && r % 2000 == 0 && r > 0) {
printf(" Processing modulo group: %d / %lld...\n", r, c_val);
}
int len = rem_counts[r];
if (len < 2) continue;
for (int zi = 1; zi < len; zi++) {
long long z = groups[r][zi];
int128 z4 = pow4[z];
for (int xi = 0; xi < zi; xi++) {
long long x = groups[r][xi];
int128 val = (z4 - pow4[x]) / c_val;
int rem_f = (int)(val % filter_mod);
if (filter_table[rem_f] == 0) continue;
if (count >= capacity) {
capacity = capacity * 1.2 + 1000;
all_nodes = (SolutionNode*)realloc(all_nodes, capacity * sizeof(SolutionNode));
}
all_nodes[count].val = val;
all_nodes[count].x = x;
all_nodes[count].z = z;
count++;
}
}
}
long long total_nodes = count;
printf("Total nodes collected after filter: %lld\n", total_nodes);
free(filter_table);
// ==========================================
// 3. Create Hash Index for Fast Search
// ==========================================
printf("[3/4] Creating hash index table...\n");
HashBucket *buckets = (HashBucket*)calloc(hash_mod, sizeof(HashBucket));
for (long long i = 0; i < total_nodes; i++) {
int hash = (int)(all_nodes[i].val % hash_mod);
buckets[hash].count++;
}
uint32_t sum = 0;
for (int i = 0; i < hash_mod; i++) {
buckets[i].offset = sum;
sum += buckets[i].count;
buckets[i].count = 0;
}
if (verbose) printf(" Sorting nodes into continuous bucket memory...\n");
SolutionNode *sorted_nodes = (SolutionNode*)malloc(total_nodes * sizeof(SolutionNode));
for (long long i = 0; i < total_nodes; i++) {
int hash = (int)(all_nodes[i].val % hash_mod);
uint32_t pos = buckets[hash].offset + buckets[hash].count;
sorted_nodes[pos] = all_nodes[i];
buckets[hash].count++;
}
free(all_nodes);
if (verbose) printf(" Performing binary-search preparation (qsort) on buckets...\n");
for (int i = 0; i < hash_mod; i++) {
if (buckets[i].count > 1) {
qsort(sorted_nodes + buckets[i].offset, buckets[i].count, sizeof(SolutionNode), compare_nodes);
}
}
// ==========================================
// 4. Generate y^4 - w^4 and Search
// ==========================================
printf("[4/4] Generating y^4 - w^4 and performing main search...\n");
int128 max_limit = pow4[n_val] / c_val;
long long interval = (n_val < 500000) ? 50000 : 100000;
for (long long y = 2; y <= n_val; y++) {
if (verbose && y % interval == 0) {
printf(" Current progress: y = %lld / %lld...\n", y, n_val);
}
int128 y4 = pow4[y];
for (long long w = y - 1; w >= 1; w--) {
int64 g=igcd(y,w);
int64 gg;
int128 target = y4 - pow4[w];
if (target > max_limit) break;
int hash = (int)(target % hash_mod);
uint32_t start = buckets[hash].offset;
uint32_t end = start + buckets[hash].count;
uint32_t low = start, high = end;
while (low < high) {
uint32_t mid = low + (high - low) / 2;
if (sorted_nodes[mid].val == target) {
if (sorted_nodes[mid].x != w && sorted_nodes[mid].x != y) {
gg=igcd(g,igcd(sorted_nodes[mid].x, sorted_nodes[mid].z));
if(gg==1){
nsol++;
/* printf("\n[SOLUTION FOUND]\n"); */
/* printf("x= %lld, y = %lld, z = %lld, w = %lld\n", sorted_nodes[mid].x, y, sorted_nodes[mid].z, w); */
printf("%lld^4+%lld*%lld^4=%lld^4+%lld*%lld^4\n", sorted_nodes[mid].x/gg, c_val, y/gg, sorted_nodes[mid].z/gg, c_val, w/gg);
/*
printf("Verification:\n");
print128(pow4[sorted_nodes[mid].x] + (int128)c_val * pow4[y]); printf("\n==\n");
print128(pow4[sorted_nodes[mid].z] + (int128)c_val * pow4[w]); printf("\n");
*/
}
break;
}
}
else if (sorted_nodes[mid].val < target) low = mid + 1;
else high = mid;
}
}
}
for(int i = 0; i < c_val; i++) if(groups[i]) free(groups[i]);
free(groups); free(rem_counts); free(rem_idx);
free(pow4); free(sorted_nodes); free(buckets);
printf("\nFound %ld solutions.\n", nsol);
printf("Search finished successfully.\n");
return 0;
}
700000までの範囲で調べたところ
朝の時点で未解決だった
9562, 10463, 11354, 12527, 13178, 15117, 15234, 15427, 15727, 15815,
16063, 17026, 17133, 17167, 17230, 17315, 17386, 17405, 17481, 17495,
17529, 17773, 17791, 17801, 17903, 17977, 17994, 18074, 18141, 18311,
18372, 18453, 18471, 18498, 18898, 19002, 19077, 19085, 19117, 19219,
19290, 19297, 19321, 19531, 19661, 19834, 19977
の47個「???」のうち
12527, 15234, 15727, 16063, 17026, 17167, 17315, 17386, 17791, 17801,
17903, 18074, 18141, 18498, 18898, 19002, 19077, 19085, 19290, 19297,
19321, 19834, 19977
の23個は解決し、残りは
9562, 10463, 11354, 13178, 15117, 15427, 15815, 17133, 17230, 17405,
17481, 17495, 17529, 17773, 17977, 17994, 18311, 18372, 18453, 18471,
19117, 19219, 19531, 19661
の24個となりました。
＞らすかるさん
Seiji Tomitaのデータですが、h=9719のデータ
9719 195094869572512833 14377568349438717 62388694687774103 20884354073695547
には、???が付いていませんが、整数解は17～18桁なので、Brute-force-searchや他の方法によって、最小解であることを証明できるとはとても思えないので、おそらく???の付け忘れでしょう。
最小解の未解決リストに追加が必要です。
9719の最小解はここで回答したこともあって解決済みで、
No.3279の解決済み最小解リストに含まれています。
ところで、8712の解はひどいですね。おそらく書き間違いかとは思いますが。
Seiji Tomitaのデータのn=8712のときの行
8712 121 3 121 3
は自明な整数解です(おそらく編集ミスでしょう)。
n=8712のときの最小解ですが、max{x,y,z,w}<=100000の範囲の検索で、
3338^4+8712*6209^4=59966^4+8712*1191^4
であることを確認しました。
[dqde4によるBrute-force-searchの実行ログ]
-bash-3.1$ time ./dqde4 8712 -m 100000
--- Diophantine Equation A^4 + h*B^4 = C^4 + h*D^4 Search Started ---
Settings: h = 8712, N = 100000, FILTER_MOD = 1360, HASH_MOD = 9999991, Verbose = OFF
[2/4] Computing and filtering (z^4 - x^4) / h...
Total nodes collected after filter: 1745960
[3/4] Creating hash index table...
[4/4] Generating y^4 - w^4 and performing main search...
3338^4+8712*6209^4=59966^4+8712*1191^4
30668^4+8712*6907^4=56056^4+8712*5939^4
Found 2 solutions.
Search finished successfully.
real 0m24.472s
user 0m24.228s
sys 0m0.230s
n=19613のときの最小解は、max{x,y,z,w}<=300000の範囲の検索で、
78443^4+19613*28018^4=196139^4+19613*27142^4
であることを確認しました。
[dqde4によるBrute-force-searchの実行ログ]
-bash-3.1$ time ./dqde4 19613 -m 300000
--- Diophantine Equation A^4 + h*B^4 = C^4 + h*D^4 Search Started ---
Settings: h = 19613, N = 300000, FILTER_MOD = 1360, HASH_MOD = 9999991, Verbose = OFF
[2/4] Computing and filtering (z^4 - x^4) / h...
Total nodes collected after filter: 2506139
[3/4] Creating hash index table...
[4/4] Generating y^4 - w^4 and performing main search...
78443^4+19613*28018^4=196139^4+19613*27142^4
Found 1 solutions.
Search finished successfully.
real 2m29.779s
user 2m29.396s
sys 0m0.320s
8712の最小解は二つ目の方(z=56056)ですね。
・・・と書いてから不安になったのですが、確か「最小解」は「max{|x|,|y|,|z|,|w|}が最小の解」でしたよね？
「式の値が最小」という考え方もありますが・・・
>らすかるさん
>「最小解」は「max{|x|,|y|,|z|,|w|}が最小の解」でしたよね？
>「式の値が最小」という考え方もありますが・・・
整数解をソートするのをさぼって、間違えました。
「max{|x|,|y|,|z|,|w|}が最小の解」の方が簡単なので、こちらを採用します。
(「{x^4+h*y^4}が最小の解」という別の定義もありますが、計算がやや面倒なので、こちらは使いません。)
最初の定義を採用すると、n=8712のときの最小解は、
30668^4+8712*6907^4=56056^4+8712*5939^4 (正)
3338^4+8712*6209^4=59966^4+8712*1191^4 (誤)
です。
h=19661のときの最小解は、max{x,y,z,w}<=1500000の範囲の検索により、
1158403^4+19661*89009^4=1319397^4+19661*21687^4
であることを確認しました。
[dqde4によるBrute-force-searchの実行ログ]
-bash-3.1$ time ./dqde4 19661 -m 1500000
--- Diophantine Equation A^4 + h*B^4 = C^4 + h*D^4 Search Started ---
Settings: h = 19661, N = 1500000, FILTER_MOD = 1360, HASH_MOD = 9999991, Verbose = OFF
[2/4] Computing and filtering (z^4 - x^4) / h...
Total nodes collected after filter: 63021950
[3/4] Creating hash index table...
[4/4] Generating y^4 - w^4 and performing main search...
1158403^4+19661*89009^4=1319397^4+19661*21687^4
Found 1 solutions.
Search finished successfully.
real 142m28.110s
user 142m22.169s
sys 0m5.934s
No.3281で書いた、自分で解決した分の式を書いておきます。
425132^4 + 12527 * 14131^4 = 426704^4 + 12527 * 5747^4
520329^4 + 15234 * 42430^4 = 591753^4 + 15234 * 7790^4
230261^4 + 15727 * 39342^4 = 387531^4 + 15727 * 32678^4
440997^4 + 16063 * 51262^4 = 619161^4 + 16063 * 18236^4
105984^4 + 17026 * 30833^4 = 336692^4 + 17026 * 19887^4
572204^4 + 17167 * 53032^4 = 612319^4 + 17167 * 49421^4
171491^4 + 17315 * 70396^4 = 347959^4 + 17315 * 69818^4
41788^4 + 17386 * 32829^4 = 374536^4 + 17386 * 13149^4
121804^4 + 17791 * 56978^4 = 607627^4 + 17791 * 41231^4
272546^4 + 17801 * 129029^4 = 602246^4 + 17801 * 128197^4
208469^4 + 17903 * 26231^4 = 310718^4 + 17903 * 15538^4
177771^4 + 18074 * 30501^4 = 351539^4 + 18074 * 16591^4
495752^4 + 18141 * 16401^4 = 495956^4 + 18141 * 16081^4
186742^4 + 18498 * 33563^4 = 396386^4 + 18498 * 3131^4
340211^4 + 18898 * 37263^4 = 472403^4 + 18898 * 6303^4
181379^4 + 19002 * 29336^4 = 350677^4 + 19002 * 6462^4
406190^4 + 19077 * 42719^4 = 469780^4 + 19077 * 38531^4
204161^4 + 19085 * 30145^4 = 355453^4 + 19085 * 16837^4
279365^4 + 19290 * 53534^4 = 542995^4 + 19290 * 44784^4
18288^4 + 19297 * 44987^4 = 530078^4 + 19297 * 8199^4
232027^4 + 19321 * 30141^4 = 308961^4 + 19321 * 26641^4
115259^4 + 19834 * 48649^4 = 484931^4 + 19834 * 40987^4
134026^4 + 19977 * 39329^4 = 332104^4 + 19977 * 36627^4
それ以降に解決したのは以下の6個です。
60862^4 + 13178 * 93997^4 = 703462^4 + 13178 * 87821^4
99753^4 + 15117 * 69854^4 = 764901^4 + 15117 * 32908^4
527295^4 + 17481 * 69662^4 = 836223^4 + 17481 * 970^4
80731^4 + 17529 * 82357^4 = 863693^4 + 17529 * 61453^4
446938^4 + 17773 * 72683^4 = 761626^4 + 17773 * 57877^4
421119^4 + 17994 * 144064^4 = 856455^4 + 17994 * 141650^4
19661はNakaoさんに解決していただきましたので、残りの「???」は
9562, 10463, 11354, 15427, 15815, 17133, 17230, 17405, 17495, 17977,
18311, 18372, 18453, 18471, 19117, 19219, 19531
の17個となっています。
特に9562と15427に集中して解を探しているのですが、この二つはなかなか見つかりません。
(追記) 17405は見つかりました。
(追記) 18453も見つかりました。
(追記) 10463も見つかりました。
(追記) ???以外で10000000以上の値を含むものはすべて最小解ではなく、最小解に修正したところ???以外で8桁以上の数はなくなりました。
(追記) 17133と17230も見つかりました。???の残りは以下の12個。
9562, 11354, 15427, 15815, 17495, 17977, 18311, 18372, 18471, 19117, 19219, 19531
9562と15427は少なくとも450万以上、他は少なくとも140万以上であることはわかっています。
(追記 9月15日朝) 18372と19117が見つかりました。???の残りは以下の10個。
9562, 11354, 15427, 15815, 17495, 17977, 18311, 18471, 19219, 19531
n=19321のときは、らすかるさんが既に最小解
232027^4 + 19321 * 30141^4 = 308961^4 + 19321 * 26641^4
を見つけていますが、こちらでも確認できたので、計算ログを残しておきます。
[dqde4によるBrute-force-searchの実行ログ]
-bash-3.1$ time ./dqde4 19321 -m 1000000
--- Diophantine Equation A^4 + h*B^4 = C^4 + h*D^4 Search Started ---
Settings: h = 19321, N = 1000000, FILTER_MOD = 1360, HASH_MOD = 9999991, Verbose = OFF
[2/4] Computing and filtering (z^4 - x^4) / h...
Total nodes collected after filter: 21024869
[3/4] Creating hash index table...
[4/4] Generating y^4 - w^4 and performing main search...
97696^4+19321*27949^4=329548^4+19321*8173^4
232027^4+19321*30141^4=308961^4+19321*26641^4
Found 2 solutions.
Search finished successfully.
real 52m31.899s
user 52m29.975s
sys 0m1.922s
No 3280の"dqde4.c"のCソースコードの修正です。
らすかるさんのアルゴリズムの本質的な修正ではなく、-m 1500000 あたりでの必要メモリが大きいので、以下のように１行を変更すると、必要メモリを少し抑えることができます。n_val*60の定数60は、他のパラメータに合わせて、多少の調整(増加)が必要かもしれません。
(変更前)
long long capacity = (n_val < 500000) ? 5000000 : 300000000;
(変更後)
long long capacity = (n_val < 500000) ? 5000000 : (n_val < 3000000 ? n_val*60 : 300000000);
以降は、この修正を入れた"dqde4.c"を使用します。
