Project Euler problem 140
in [Math]
|
From: mukesh tiwari on 20 Apr 2010 15:42 On Apr 20, 9:54 pm, Mensanator <mensana...(a)aol.com> wrote: > On Apr 20, 9:41 am, mukesh tiwari <mukeshtiwari.ii...(a)gmail.com> > wrote: > > > Hello everyone, I am trying to solve this problem but i am not getting > > efficient solution. Here is my analysis. > > > A=(x^2+3x)/(1-x-x^2) > > x=-(A+1)+Sqrt(5A^2+14A+1)/2(A+3) since x is rational so 5A^2+14A+1 > > must be a perfect square. > > 5A^2+14A+1=D^2 > > A=-14+Sqrt(20D^2+176)/10.. This is the value of A which we have to add > > upto 30 numbers. Now i am iteration D from 1 to infinity and got some > > values but it tool almost 30 mins and produce only 21 values. > > What are you using? An abacus? > > > > > 2 > > 5 > > 21 > > 42 > > 152 > > 296 > > 1050 > > 2037 > > 7205 > > 13970 > > 49392 > > 95760 > > 338546 > > 656357 > > 2320437 > > 4498746 > > 15904520 > > 30834872 > > 109011210 > > 211345365 > > 747173957 > > kindly give me some more insights. > > Thank you I think you are asking about numbers. I generated it using computer program.
From: I.M. Soloveichik on 20 Apr 2010 12:49 Your problem can be reformulated as solving Pell's Equation, x^2-Dy^2=N, except that you have an extra condition on the congruence class of x. I don't know if the theory can explain how to get all these solutions, but certainly theory should say there are infinitely many. It is interesting that your kth solution is roughly e^k. im > Hello everyone, I am trying to solve this problem but > i am not getting > efficient solution. Here is my analysis. > > A=(x^2+3x)/(1-x-x^2) > x=-(A+1)+Sqrt(5A^2+14A+1)/2(A+3) since x is rational > so 5A^2+14A+1 > must be a perfect square. > 5A^2+14A+1=D^2 > A=-14+Sqrt(20D^2+176)/10.. This is the value of A > which we have to add > upto 30 numbers. Now i am iteration D from 1 to > infinity and got some > values but it tool almost 30 mins and produce only 21 > values. > 2 > 5 > 21 > 42 > 152 > 296 > 1050 > 2037 > 7205 > 13970 > 49392 > 95760 > 338546 > 656357 > 2320437 > 4498746 > 15904520 > 30834872 > 109011210 > 211345365 > 747173957 > kindly give me some more insights. > Thank you
From: Mensanator on 20 Apr 2010 20:57
On Apr 20, 2:42 pm, mukesh tiwari <mukeshtiwari.ii...(a)gmail.com> wrote: > On Apr 20, 9:54 pm, Mensanator <mensana...(a)aol.com> wrote: > > > > > > > On Apr 20, 9:41 am, mukesh tiwari <mukeshtiwari.ii...(a)gmail.com> > > wrote: > > > > Hello everyone, I am trying to solve this problem but i am not getting > > > efficient solution. Here is my analysis. > > > > A=(x^2+3x)/(1-x-x^2) > > > x=-(A+1)+Sqrt(5A^2+14A+1)/2(A+3) since x is rational so 5A^2+14A+1 > > > must be a perfect square. > > > 5A^2+14A+1=D^2 > > > A=-14+Sqrt(20D^2+176)/10.. This is the value of A which we have to add > > > upto 30 numbers. Now i am iteration D from 1 to infinity and got some > > > values but it tool almost 30 mins and produce only 21 values. > > > What are you using? An abacus? > > > > 2 > > > 5 > > > 21 > > > 42 > > > 152 > > > 296 > > > 1050 > > > 2037 > > > 7205 > > > 13970 > > > 49392 > > > 95760 > > > 338546 > > > 656357 > > > 2320437 > > > 4498746 > > > 15904520 > > > 30834872 > > > 109011210 > > > 211345365 > > > 747173957 > > > kindly give me some more insights. > > > Thank you > > I think you are asking about numbers. I generated it using computer > program. But are you, in fact, iterating from 1 to infinity? If so, you may as well be using an abacus for all the good it will do you. I don't know project Euler that well, but I think their problems aren't supposed to be easy to solve with brute force iteration as you have discovered. Take the hints about Pell and see if you can get close the answer to at least minimize the brute force searching. Look at the ratios of the last two numbers. There's a pattern there that can be exploited. You ought to be able to make a very close guess as to where the next number is. Brute force seaching from the guess will be much quicker than doing ALL the numbers from the previous answer. My quick and dirty guesses got all your results in less than a minute. |