Diophantine equation
I feel this is the most difficult problem in the first 100 PE problems(at least, the top five). This diophantine equation is called Pell Equation, which can be seen in every elementary number theory books. I should admit that I cheated on this problem. I did not solve this problem, but google helped me to find out the answer. This time, I solved it with the help of wikipedia and wolfram mathworld.
It is a very interesting problem! x^2-61y^2=1 with solution x=1766319049, y=226153980 is a notorious diophantine equation in the math history.
I tried to change D upto 100000, I found that the value of x and y are
9138623307350640837938507246130056541284450249628186652711211526290141593088447074959889691586109808446586788487329855457947449359122812196406183471094085243300140113776722320673519989258197664615506581635543258793642137960637895993371068043922291726707457424732865511811603416709407607285667077345150397643032877987726841522351750655900253781916899660152174806370963781778224969807395941841736594668461346490187409918540644500596164105739747237839541686461147582701486262272823400803243678345216257264359841059899047944315969645240323636858831783554703663860186919961543958325467259751629633944639211198469786177829884186709831569216425531620090438319686256712276877552760998820897069126292769743115626179169131031894821449
29995606985908278391394125599135320972040960690735594014932999302562021607917845625308781046774668965028391500344676078764117785968987025596642346687378667667268554217805689486419938846247966636235622466824853671443727025761340681500617596724921086840802447598463611192953164168684707145263201173090354218890224078617132621981270144387271894050379162839910605924620561997843353743092508084766465038567232036892276652930541497664634108271302723027950641070447197899109815123567584348859003464872979489356061130456764804964145771699318883015346111831572404557647659469760522059443590269944115798752448599110602793086535348170280145151753392282563680433826089979371590683960862942643266548255841329663100421901070962552821740
when D = 92821
It is amazing to find these two more than 700 digits numbers in less than 20 seconds with my x220 notebook.
09/21/2017: did the same thing with python with much easier implementation
No comments:
Post a Comment