## 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

Don't post any spoilers
viv_ban
Posts: 23
Joined: Mon May 26, 2008 3:09 pm

### Re: prob-192(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.
David F
Posts: 23
Joined: Sun Jul 20, 2008 11:03 pm

### Re: prob-192(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).
stijn263
Posts: 1505
Joined: Sat Sep 15, 2007 11:57 pm
Location: Netherlands

### Re: prob-192(best rational approx)

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
hk
Posts: 10984
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

### Re: prob-192(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.
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.
Tommy137
Posts: 238
Joined: Sun Feb 24, 2008 6:02 pm
Location: Cologne, Germany
Contact:

### 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.
karlo
Posts: 107
Joined: Tue Dec 02, 2008 5:32 pm
Location: Cambridge, MA
Contact:

### 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.
ThomasH
Posts: 117
Joined: Sun Mar 26, 2006 8:41 am
Location: Berlin, Germany

### Re: Help with 192

You are welcome - send a PM to me.
ThomasH
Posts: 117
Joined: Sun Mar 26, 2006 8:41 am
Location: Berlin, Germany

### Re: Help with 192

mdean
Posts: 169
Joined: Tue Aug 02, 2011 2:05 am

### 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.
thundre
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

### Re: Problem 192

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.
mdean
Posts: 169
Joined: Tue Aug 02, 2011 2:05 am

### Re: Problem 192

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.
hk
Posts: 10984
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

### Re: Problem 192

Please read Daniel.is.Fisher's post of 4 May 2008 1.15 am on that forum.
DeKlod
Posts: 19
Joined: Tue Aug 21, 2018 8:55 am

### 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
FreeCaenepeel
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
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: 63
Joined: Sat Oct 11, 2008 12:24 pm

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