Problem 192

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
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.

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


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
viv_ban
Posts: 23
Joined: Mon May 26, 2008 2:09 pm

Re: prob-192(best rational approx)

Post by viv_ban »

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.

David F
Posts: 23
Joined: Sun Jul 20, 2008 10:03 pm

Re: prob-192(best rational approx)

Post by David F »

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).

User avatar
stijn263
Posts: 1505
Joined: Sat Sep 15, 2007 10:57 pm
Location: Netherlands

Re: prob-192(best rational approx)

Post by stijn263 »

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).
Yup. I thought it was PE policy that having BigNum shouldn't give one this big an advantage over people who don't..

edit: And I think it's a great policy!! Maple is awfully slow, and I'm too lazy to get gmp working ;)

User avatar
hk
Administrator
Posts: 10706
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

Re: prob-192(best rational approx)

Post by hk »

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.
Image

User avatar
JamieCamardelle
Posts: 20
Joined: Wed May 14, 2008 4:34 am

problem 192

Post by JamieCamardelle »

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.

User avatar
Tommy137
Posts: 238
Joined: Sun Feb 24, 2008 6:02 pm
Location: Cologne, Germany
Contact:

Re: problem 192

Post by Tommy137 »

Your result is way too low :?
Image

User avatar
JamieCamardelle
Posts: 20
Joined: Wed May 14, 2008 4:34 am

Re: problem 192

Post by JamieCamardelle »

Thanks. Serves me right - I was trying a lazy way out. :?

karlo
Posts: 107
Joined: Tue Dec 02, 2008 5:32 pm
Location: Cambridge, MA
Contact:

Problem 192

Post by karlo »

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.

ThomasH
Posts: 117
Joined: Sun Mar 26, 2006 7:41 am
Location: Berlin, Germany

Re: Help with 192

Post by ThomasH »

You are welcome - send a PM to me.

ThomasH
Posts: 117
Joined: Sun Mar 26, 2006 7:41 am
Location: Berlin, Germany

Re: Help with 192

Post by ThomasH »

Your denominator is wrong.

mdean
Posts: 156
Joined: Tue Aug 02, 2011 1:05 am

Re: Problem 192

Post by mdean »

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.
Image

thundre
Posts: 356
Joined: Sun Mar 27, 2011 9:01 am

Re: Problem 192

Post by thundre »

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.
That should be enough precision to compare two prospective answers, but I don't see where you find enough time to perform the calculation 1017 times. You're probably not trying some of the correct denominators.

The intended solution is a well-known algorithm, and it can be implemented with 64-bit arithmetic.
Image

mdean
Posts: 156
Joined: Tue Aug 02, 2011 1:05 am

Re: Problem 192

Post by mdean »

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 1017 times. You're probably not trying some of the correct denominators.

The intended solution is a well-known algorithm, and it can be implemented with 64-bit arithmetic.
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}=$

82.219219164377862631971232155251

and $\dfrac{82094249361619}{998480041479}=$

82.219219164377862631971232161351

necessitating another plan of attack.
Image

User avatar
hk
Administrator
Posts: 10706
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

Re: Problem 192

Post by hk »

Please read Daniel.is.Fisher's post of 4 May 2008 1.15 am on that forum.
Image

DeKlod
Posts: 17
Joined: Tue Aug 21, 2018 7:55 am

Re: Problem 192

Post by DeKlod »

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

FreeCaenepeel
Posts: 1
Joined: Sat Mar 28, 2020 2:32 pm

Re: Problem 192

Post by FreeCaenepeel »

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.432420812874472099060302734375E-15

whereas for the second fraction it is indeed larger
6.432420816296734800060302734375E-15

I use Decimal() in Python to do the divisions.

DJohn
Posts: 57
Joined: Sat Oct 11, 2008 11:24 am

Re: Problem 192

Post by DJohn »

62831818251916/902212330695 is correct. The differences are very small, and the sort of error you get from floating point approximations will be much greater.

Post Reply