Problem 192
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.
This forum is NOT meant to discuss solution methods for a problem.
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.
This forum is NOT meant to discuss solution methods for a problem.
In particular don't post any code fragments or results.
Don't start begging others to give partial answers to problems
Don't ask for hints how to solve a problem
Don't start a new topic for a problem if there already exists one
Don't start begging others to give partial answers to problems
Don't ask for hints how to solve a problem
Don't start a new topic for a problem if there already exists one
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Re: prob192(best rational approx)
thanks david,
Finally I get the right answer of the question. The precision involved in this particular question really screwed me. Initially I thought the problem was with my algorithm but the actual problem was with my precision which should atleast be equal to 60 decimal places.
Finally I get the right answer of the question. The precision involved in this particular question really screwed me. Initially I thought the problem was with my algorithm but the actual problem was with my precision which should atleast be equal to 60 decimal places.
Re: prob192(best rational approx)
Pity those of us without BigNum support who had to work something else out. (I did it essentially the same as daniel.is.fischer's posted algorithm in the solution thread).
Re: prob192(best rational approx)
Yup. I thought it was PE policy that having BigNum shouldn't give one this big an advantage over people who don't..David F wrote:Pity those of us without BigNum support who had to work something else out. (I did it essentially the same as daniel.is.fischer's posted algorithm in the solution thread).
edit: And I think it's a great policy!! Maple is awfully slow, and I'm too lazy to get gmp working
Re: prob192(best rational approx)
p192 can be solved with bignums, but at a considerable speed loss.
Moreover there is the follow up of p198. If one did not really understand what p192 was about and "cheated" with bignums p198 is considerably more difficult. (at least if one does not take the lessons given in the forum of p192)
Many complaints about p198 can be based on that.
Moreover there is the follow up of p198. If one did not really understand what p192 was about and "cheated" with bignums p198 is considerably more difficult. (at least if one does not take the lessons given in the forum of p192)
Many complaints about p198 can be based on that.
 JamieCamardelle
 Posts: 20
 Joined: Wed May 14, 2008 5:34 am
problem 192
Can anyone confirm or deny that the sum of the denominators of the best appromations for sqrt[n] with denominator bound 10^12 as n goes from 2 to 100 and n is not a perfect square is 757577250?
I am trying something out with AffineRationalize in Mathematica.
I am trying something out with AffineRationalize in Mathematica.
Re: problem 192
Your result is way too low
 JamieCamardelle
 Posts: 20
 Joined: Wed May 14, 2008 5:34 am
Re: problem 192
Thanks. Serves me right  I was trying a lazy way out.
Problem 192
I am trying to solve 192. I first did the examples given in the problem and got the answers. I am not sure though that the method I am using is correct. Is there anyone whom I could send my fraction for sqrt(13) and the bound 10**12, and tell me if it's right? Thanks.
Re: Help with 192
You are welcome  send a PM to me.
Re: Help with 192
Your denominator is wrong.
Re: Problem 192
It seems this problem is going to haunt me. I even wrote my first program in C# to take advantage of the 128 bit decimal type with 29 digits of precision and it's still wrong. I've got to be missing something.
Re: Problem 192
That should be enough precision to compare two prospective answers, but I don't see where you find enough time to perform the calculation 10^{17} times. You're probably not trying some of the correct denominators.mdean wrote:It seems this problem is going to haunt me. I even wrote my first program in C# to take advantage of the 128 bit decimal type with 29 digits of precision and it's still wrong. I've got to be missing something.
The intended solution is a wellknown algorithm, and it can be implemented with 64bit arithmetic.
Re: Problem 192
I don't know where that $10^{17}$ comes from. I've posted in the solutions thread by the way (didn't break 1 minute, but less than 10). With my original method, C# was unable to compare $\sqrt{6760}=$thundre wrote:That should be enough precision to compare two prospective answers, but I don't see where you find enough time to perform the calculation 10^{17} times. You're probably not trying some of the correct denominators.
The intended solution is a wellknown algorithm, and it can be implemented with 64bit arithmetic.
82.219219164377862631971232155251
and $\dfrac{82094249361619}{998480041479}=$
82.219219164377862631971232161351
necessitating another plan of attack.
Re: Problem 192
Please read Daniel.is.Fisher's post of 4 May 2008 1.15 am on that forum.
Re: Problem 192
Hi all,
I'm going slightly mad here: fairly sure my algorithm is right (gives 902212330695 for sqrt(4850) anyway), but can't seem to get the right answer. Any volunteers for a PM to validate my method and/or some other examples?
Cheers,
Claude
I'm going slightly mad here: fairly sure my algorithm is right (gives 902212330695 for sqrt(4850) anyway), but can't seem to get the right answer. Any volunteers for a PM to validate my method and/or some other examples?
Cheers,
Claude

 Posts: 1
 Joined: Sat Mar 28, 2020 2:32 pm
Re: Problem 192
Shouldn't the best approximation for the square root of 4850
be 22555308267375/323875351814
instead of
62831818251916/902212330695
the distance to sqrt(4850) for the first fraction is
6.432420812874472099060302734375E15
whereas for the second fraction it is indeed larger
6.432420816296734800060302734375E15
I use Decimal() in Python to do the divisions.
be 22555308267375/323875351814
instead of
62831818251916/902212330695
the distance to sqrt(4850) for the first fraction is
6.432420812874472099060302734375E15
whereas for the second fraction it is indeed larger
6.432420816296734800060302734375E15
I use Decimal() in Python to do the divisions.
Re: Problem 192
62831818251916/902212330695 is correct. The differences are very small, and the sort of error you get from floating point approximations will be much greater.