project euler problem 223

Almost right-angled triangles I, Revisit

This problem is very difficult.  One algorithm is easy to come up with. But it is not very efficient. It is quite slow. My code runs for 20 seconds. Doraki provided a very nice algorithm in the first page.  It only takes a few seconds using Doraki's algorithm. I am very eager to know if there is any efficient method to solve it in one second.

project euler problem 176

Rectangular triangles that share a cathetus

The problem looks like extremely difficult. But if you see this problem as a diophantine equation, it is not that difficult. Actually it can be calculated with a calculator. 

project euler problem 157

Solving the diophantine equation 1/a+1/b= p/10^n

This is a very simple problem. I did not see why only 1200 people solved it. If we can rephrase it, everybody can solve it. Actually, the list is a good hint, one need to investigate the list a little bit or reorder it.

project euler problem 110

Diophantine reciprocals II

This problem is not so easy. But since we have already solved problem 108, this problem becomes much easier. I have a very loose bound on the power of each prime, still only takes 8ms to get the answer.

project euler problem 108

Diophantine reciprocals I

My old code is too ugly and complicated. I do not want to read it. 
 This time I rewrote my code, it is easy to read and runs pretty fast, only 0.3 second. But after I read the discussion, I felt that I should think more about how to solve this diophantine equation before writing the code.  This could be a serious issue when the problem becomes more difficult. 

If you did not give too much analytical analysis on this problem, please learn from the discussion.

project euler problem 066

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