## 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
JohnMorris
Posts: 64
Joined: Sun Dec 23, 2007 6:38 am

### P192 clarification

Problem 192 says:
Find the sum of all denominators of the best approximations to âˆšn for the denominator 1012, where n is not a perfect square and 1 < n [le] 100000.
I think I understand the question (even if I can't solve it yet), but it appears that "denominator" is being used twice in the same sentence to mean two different things, which confused me initially. Should it be disambiguated?
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11:15 pm
Location: Bremen, Germany

### Re: P192 clarification

Have you a suggestion?

Edit: I introduced the term "denominator bound", is that better?
Il faut respecter la montagne -- c'est pourquoi les gypa&egrave;tes sont l&agrave;.
Georg
Posts: 157
Joined: Mon Jan 21, 2008 7:00 am
Location: Mannheim, Germany
Contact:

### Re: P192 clarification

daniel.is.fischer wrote:Edit: I introduced the term "denominator bound", is that better?
I had no problem to understand it after your correction, when I read P192 for the first time.
stijn263
Posts: 1505
Joined: Sat Sep 15, 2007 11:57 pm
Location: Netherlands

### Re: P192 clarification

Are there any solutions yet where everything fits into 64 bit integers and/or double precision floats ? All the approaches I can think of require either to multiply or to divide two 11 digit numbers..
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11:15 pm
Location: Bremen, Germany

### Re: P192 clarification

My solution fits in 64 bit integers. Excepting the denominators themselves, everything's 32 bits.
Il faut respecter la montagne -- c'est pourquoi les gypa&egrave;tes sont l&agrave;.
Tommy137
Posts: 238
Joined: Sun Feb 24, 2008 6:02 pm
Location: Cologne, Germany
Contact:

### Re: P192 clarification

I must admit that I do not fully understand your solution, daniel
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11:15 pm
Location: Bremen, Germany

### Re: P192 clarification

I'll explain. Might take a moment, though.

Il faut respecter la montagne -- c'est pourquoi les gypa&egrave;tes sont l&agrave;.
stijn263
Posts: 1505
Joined: Sat Sep 15, 2007 11:57 pm
Location: Netherlands

### Re: P192 clarification

Don't feel like making a biginter class in C++ so I'm just going to let my program run overnight in Maple
sfabriz
Posts: 175
Joined: Thu Apr 06, 2006 12:18 am
Location: London - UK

### Re: P192 clarification

Let suppose n=4850
using double precision (64 bit) I get sqrt(n) = 69,6419413859206

Now, my program evaluates this to have best approximation to:
67819583637568 / 973832467733 = 69,641941385920600000000000205374

If I use Biginteger, adding some precision, I get sqrt(n) = 69,641941385920596692338694642566468530971982030564030346201369
which yields as best approximation:
62831818251916 / 902212330695 = 69,641941385920596692338692931435

Let's check:

Code: Select all

69,641941385920596692338692931435 (BigInteger)
69,641941385920600000000000205374 (double precision)
69,641941385920596692338694642566468530971982030564030346201369 (real value)
Now, as you can see the one I got using BigIntegers is far better. Is that correct? Because when I run my proggy on the examples I get everything right, but no way I can get the correct solution.

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

### Re: P192 clarification

902212330695 is correct.
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11:15 pm
Location: Bremen, Germany

### Re: P192 clarification

stijn263 wrote:Don't feel like making a biginter class in C++ so I'm just going to let my program run overnight in Maple
Ever thought of using Java? Or GMP? But you don't need bignums, anyway
Il faut respecter la montagne -- c'est pourquoi les gypa&egrave;tes sont l&agrave;.
rayfil
Posts: 1406
Joined: Sun Mar 26, 2006 5:30 am
Contact:

### Re: P192 clarification

64 bit integers and/or double precision floats ?
For those following this thread and who may not yet be aware of it, double precision floats (often referred as 64-bit floats) only have a precision of 53 bits, one of them being implied. One bit is used for the sign, and 11 bits used for the biased exponent.

In order to have 64-bit precision with floats, one needs to use extended double precision, i.e. 80-bit floats. (One bit is used for the sign, and 15 bits used for the biased exponent.)
When you assume something, you risk being wrong half the time.
sfabriz
Posts: 175
Joined: Thu Apr 06, 2006 12:18 am
Location: London - UK

### Re: P192 clarification

Tommy137 wrote:902212330695 is correct.
Allright, thank you.
Now I'm 1/99684 done with this problem...

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

### Re: P192 clarification

sfabriz wrote:
Tommy137 wrote:902212330695 is correct.
Allright, thank you.
Now I'm 1/99684 done with this problem...

Cheers
It seems you solved it though
stijn263
Posts: 1505
Joined: Sat Sep 15, 2007 11:57 pm
Location: Netherlands

### Re: P192 clarification

daniel.is.fischer wrote:
stijn263 wrote:Don't feel like making a biginter class in C++ so I'm just going to let my program run overnight in Maple
Ever thought of using Java? Or GMP? But you don't need bignums, anyway
My Maple program just finished, I was really happy my algorithm was correct

However it seems almost all solutions use bignums..
sfabriz
Posts: 175
Joined: Thu Apr 06, 2006 12:18 am
Location: London - UK

### Re: P192 clarification

Tommy137 wrote:
sfabriz wrote:
Tommy137 wrote:902212330695 is correct.
Allright, thank you.
Now I'm 1/99684 done with this problem...

Cheers
It seems you solved it though
Yep, my algo was correct, but I had 50 digits precision and it turned out they weren't enough. 60 have been good.

Cheers
viv_ban
Posts: 23
Joined: Mon May 26, 2008 3:09 pm

### prob-192(best rational approx)

the answer generated by my program is equal to 610031050010701
funktio
Posts: 14
Joined: Mon May 19, 2008 6:55 pm
Location: Helsinki, Finland

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

I get a slightly smaller number.
for($"=@_=split??,"Jrsk an treP rehlohacteu,";$";$\="\r"){$\.=$.=chr 32+95*rand,$_-$"or$.ne$_[--$"%2?-$"-1:$"]&&$"++for++$|..\$";print}<>
viv_ban
Posts: 23
Joined: Mon May 26, 2008 3:09 pm

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

is the answer to my question = 561480917932597
David F
Posts: 23
Joined: Sun Jul 20, 2008 11:03 pm

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

I believe so, yes.