梅森平方根-ProjectEuler 942
ProjectEuler 942 有一道题:https://projecteuler.net/problem=942如果我们能找到最小的正整数$x$,使得方程$x^2-q=y(2^q-1)$有正整数解, 我们称$x$是$q$的梅森平方根$x=R(q)$. 比如,$R(5)=6, R(13)=3126, R(17)=47569, R(29)=128075238$
求 $R(74207281)$ 对$10^9+7$取模的结果
我简单算了下,不考虑q为平方数的情况.
{5,{6,25},{31}}
{13,{3126,5065},{8191}}
{17,{47569,83502},{131071}}
{29,{128075238,141439186,194896081,208260029,328610882,341974830,395431725,408795673},{536870911}}
{37,{54698065206,60244928799,77194024672,82740888265},{137438953471}}
{41,{419978300024,657039159697,1541984095854,1779044955527},{2199023255551}}
{53,{1612847830752678,2173950773799266,3395191604584057,3956294547630645,5050904707110346,5612007650156934,6833248480941725,7394351423988313},{9007199254740991}}
{57,{6279640767769776,6581974978089937,14005909032746616,26867524778606329,40667082112598208,53528697858457921,61254966123434761,69998606206561397,74116581869294474,82860221952421110,90586490217397950,103448105963257663,117247663297249542,130109279043109255,137533213097765934,137835547308086095},{144115188075855871}}
{61,{1020009412652426358,1285833596561267593},{2305843009213693951}}
{73,{769751161485186685249,2091637185766124537628,2630702582713186776286,3952642035774792428228,5492090929964497999163,6814030383026103651105,7353095779973165889763,8674981804254103742142},{9444732965739290427391}}
{89,{184326027614947087125438865,434643992027743050324123246},{618970019642690137449562111}}
{93,{1397732387797042569680797462,1431844844855255201517200764,2831828189995086914490624525,4242114891635657513504371040,5661405422647384685688622751,7071692124287955284702369266,8471675469427786997675793027,8505787926485999629512196329},{9903520314283042199192993791}}
{97,{2452919851536752773245369778,12760105500638752951451896129,145696219527889922235636004542,156003405176991922413842530893},{158456325028528675187087900671}}
{101,{75529705232888630442472885981,565564369304959934013065577702,1969736831151498868980340833049,2459771495223570172550933524770},{2535301200456458802993406410751}}
{109,{93262072509840318928885269926009,297008816315439372519005476824438,352028291001414081047306564328073,555775034807013134637426771226502},{649037107316853453566312041152511}}
{113,{935465102415393538271886448129732,1250892160173628422222721671904235,1494099928378580244018198085777426,1809526986136815127969033309551929,1813821777053915433591835524312933,1972172426496657278585695043038408,2129248834812150317542670748087436,2287599484254892162536530266812911,2372456603017102139338147161960627,2687883660775337023288982385735130,2850529101135179173905644119221609,3165956158893414057856479342996112,3595288794985510637643644481579217,3910715852743745521594479705353720,4473645469624032532963593557762418,4789072527382267416914428781536921,5595521189687387840146563876903270,5910948247445622724097399100677773,6473877864325909735466512953086471,6789304922084144619417348176860974,7218637558176241199204513315444079,7534064615934476083155348539218582,7696710056294318233772010272705061,8012137114052553117722845496479564,8096994232814763094524462391627280,8255344882257504939518321910352755,8412421290572997978475297615401783,8570771940015739823469157134127258,8575066730932840129091959348888262,8890493788691075013042794572662765,9133701556896026834838270986535956,9449128614654261718789106210310459},{10384593717069655257060992658440191}}
{125,{3231082171776185181069178216979243211,5574093103035264137595395627731327109,5574105779540888630559522024413403269,5803946471495938197727752799986456843,7917116710799967587085739435165487167,8146957402755017154253970210738540741,8146970079260641647218096607420616901,10489981010519720603744314018172700799,12041208470502995536182072398394961175,12086989673294624205909700077237877290,14384219401762074492708289809147045073,14384232078267698985672416205829121233,14430000604553703162435917487989961188,14430013281059327655400043884672037348,16727243009526777942198633616581205131,16773024212318406611926261295424121246,25762271652798901320995564633546905185,25808052855590529990723192312389821300,28105282584057980277521782044298989083,28105295260563604770485908440981065243,28151063786849608947249409723141905198,28151076463355233440213536119823981358,30448306191822683727012125851733149141,30494087394614312396739753530576065256,32045314854597587329177511910798325632,34388325785856666285703729321550409530,34388338462362290778667855718232485690,34618179154317340345836086493805539264,36731349393621369735194073128984569588,36961190085576419302362303904557623162,36961202762082043795326430301239699322,39304213693341122751852647711991783220},{42535295865117307932921825928971026431}}
{137,{2948784648407832638635648531154588202334,60358154251722961518558738679663851235537,113866417611797531774689060325401473029934,171275787215112660654612150473910736063137},{174224571863520493293247799005065324265471}}
{149,{170080432001375964807183732937461975924213222,183988955375741567005634636591738595223256210,529634890977238373523508348133008972968117101,543543414351603975721959251787285592267160089},{713623846352979940529142984724747568191373311}}
{157,{25535067758548717479416208820330673751801040185,43370443143713105074886430088641907541123115236,52086534673939488820726792642801447433784189067,56659938988587858615437849272570895636814100938,69921910059103876416197013911112681223106264118,74495314373752246210908070540882129426136175989,81640923377219847223241949726182474348872243000,83211405903978629956748433095041669318797249820,99476298762384234818712170994493708138194318051,101046781289143017552218654363352903108119324871,108192390292610618564552533548653248030855391882,112765794607258988359263590178422696233885303753,126027765677775006160022754816964481820177466933,130601169992423375954733811446733930023207378804,139317261522649759700574174000893469915868452635,157152636907814147296044395269204703705190527686},{182687704666362864775460604089535377456991567871}}
{173,{595410084087379226022071052189588454278315562029134,901334591406131055183006064651766432504424837889315,1375892362301473407229851944514432640900345718374073,1681816869620225236390786956976610619126454994234254,1946376989130224421633220063188625464393673352662182,2252301496448976250794155075650803442619782628522363,2726859267344318602841000955513469651015703509007121,3032783774663070432001935967975647629241812784867302,8939837638351686273922650181636142867779586607192089,9245762145670438103083585194098320846005695883052270,9720319916565780455130431073960987054401616763537028,10026244423884532284291366086423165032627726039397209,10290804543394531469533799192635179877894944397825137,10596729050713283298694734205097357856121053673685318,11071286821608625650741580084960024064516974554170076,11377211328927377479902515097422202042743083830030257},{11972621413014756705924586149611790497021399392059391}}
{181,{666548078311905428920128117317958242818403144392028934,739183661215924294004853452425359030910236424784113807,897122670404616222369407741853636998467031833938586882,969758253308635087454133076961037786558865114330671755,1128230489204262753756115603133821116807021191146191482,1200866072108281618840840938241221904898854471538276355,1358805081296973547205395227669499872455649880692749430,1431440664200992412290120562776900660547483161084834303,1633550417530785304426573491523717706689995083282370048,1706186000434804169511298826631118494781828363674454921,1864125009623496097875853116059396462338623772828927996,1936760592527514962960578451166797250430457053221012869,2095232828423142629262560977339580580678613130036532596,2167868411327161494347286312446981368770446410428617469,2325807420515853422711840601875259336327241819583090544,2398443003419872287796565936982660124419075099975175417},{3064991081731777716716694054300618367237478244367204351}}
{193,{825518682506123974414130961576054387388523701766278436929,1135654337033165337154130288985763588652047761277495822600,3253415593872907861882737574887573648150733356500794294010,3563551248399949224622736902297282849414257416012011679681,8990652222373412303048841944118049982790453472916057346110,9300787876900453665788841271527759184053977532427274731781,11418549133740196190517448557429569243552663127650573203191,11728684788267237553257447884839278444816187187161790588862},{12554203470773361527671578846415332832204710888928069025791}}
{197,{31266778751458191981797328006669165119778705494970034337152,35720360215111731212129331935623235375199529873358300843430,165146895317262053230615929607022089940075844349490803569241,169600476780915592460947933535976160195496668727879070075519},{200867255532373784442745261542645325315275374222849104412671}}
{229,{40632131352107133950436137744439667336947278532286782125136001592846,43504086699219637206900902303940857309144663784170926501913155925495,184382820894410660743397893234573277967614700684960069881483709013803,187254776241523163999862657794074467939812085936844214258260863346452,336692122344610257418451210969727807974904352017917159543256602466924,339564077691722760674915975529228997947101737269801303920033756799573,379403526114794185961466751765265572978619462098823727718934063754381,382275481461906689217931516324766762950816847350707872095711218087030,480442811886913784211412966459861418605571774170590447299604309887881,483314767234026287467877731019362608577769159422474591676381464220530,523154215657097712754428507255399183609286884251497015475281771175338,526026171004210216010893271814900373581484269503381159852058925507987,675463517107297309429481824990553713616576535584454105137054664628459,678335472454409812685946589550054903588773920836338249513831818961108,819214206649600836222443580480687324247243957737127392893402372049416,822086161996713339478908345040188514219441342989011537270179526382065},{862718293348820473429344482784628181556388621521298319395315527974911}}
{233,{1490299960714889102021581345256028880821770443721616012516119672825688,2772969045893978869521964850754260916302319645125690711831528034646858,2877351687506009463171827264215613678542667223715028499295963822034168,3509719987320860696097375685543977260347570010099285290176849842742495,4160020772685099230672210769713845714023216425119103198611372183855338,4792389072499950463597759191042209295828119211503359989492258204563665,4896771714111981057247621604503562058068466790092697776956693991950975,6179440799291070824748005110001794093549015991496772476272102353772145,7624051894290056750121506614552256811353201952844000634052946093826446,8906720979469146517621890120050488846833751154248075333368354455647616,9011103621081177111271752533511841609074098732837413120832790243034926,9643471920896028344197300954840205190879001519221669911713676263743253,10293772706260266878772136039010073644554647934241487820148198604856096,10926141006075118111697684460338437226359550720625744611029084625564423,11030523647687148705347546873799789988599898299215082398493520412951733,12313192732866238472847930379298022024080447500619157097808928774772903},{13803492693581127574869511724554050904902217944340773110325048447598591}}
{241,{60032355206840686121481090263527484621021962208297283557915873636569345,1698002288925971661311088626078307653966280432684114019881527061603276276,1835691840630796997855506375407529377688687361067123896361685340981963275,3473661774349927973045113911222309547033945831542940632685296528948670206},{3533694129556768659166595001485837031654967793751237916243212402585239551}} 要求2^q-1是素数吗？要求q是素数吗？ 要求2^q-1是素数吗？ wayne 发表于 2025-5-20 10:54
我简单算了下,不考虑q为平方数的情况.
根据这些数据总结一个规律,就是 $x^2-q=y(2^q-1)$的通解是 ${x_0 + (2^q-1) c,y_0 + 2 x_0 c+(2^q - 1)c^2}$, $c$是任意整数.如果只是 寻找$x^2=q mod(2^q-1)$,对于小点的q还行,对于较大的q就麻烦了
页:
[1]