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

P192 clarification

Post by JohnMorris »

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?
Image
User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11:15 pm
Location: Bremen, Germany

Re: P192 clarification

Post by daniel.is.fischer »

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;.
User avatar
Georg
Posts: 157
Joined: Mon Jan 21, 2008 7:00 am
Location: Mannheim, Germany
Contact:

Re: P192 clarification

Post by Georg »

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.
User avatar
stijn263
Posts: 1505
Joined: Sat Sep 15, 2007 11:57 pm
Location: Netherlands

Re: P192 clarification

Post by stijn263 »

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..
User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11:15 pm
Location: Bremen, Germany

Re: P192 clarification

Post by daniel.is.fischer »

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;.
User avatar
Tommy137
Posts: 238
Joined: Sun Feb 24, 2008 6:02 pm
Location: Cologne, Germany
Contact:

Re: P192 clarification

Post by Tommy137 »

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

Re: P192 clarification

Post by daniel.is.fischer »

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

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

Re: P192 clarification

Post by stijn263 »

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

Re: P192 clarification

Post by sfabriz »

Can I ask a question?

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
Image
User avatar
Tommy137
Posts: 238
Joined: Sun Feb 24, 2008 6:02 pm
Location: Cologne, Germany
Contact:

Re: P192 clarification

Post by Tommy137 »

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

Re: P192 clarification

Post by daniel.is.fischer »

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 :D
Il faut respecter la montagne -- c'est pourquoi les gypa&egrave;tes sont l&agrave;.
User avatar
rayfil
Administrator
Posts: 1406
Joined: Sun Mar 26, 2006 5:30 am
Location: Quebec, Canada
Contact:

Re: P192 clarification

Post by rayfil »

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.
User avatar
sfabriz
Posts: 175
Joined: Thu Apr 06, 2006 12:18 am
Location: London - UK

Re: P192 clarification

Post by sfabriz »

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

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

Re: P192 clarification

Post by Tommy137 »

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

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

Re: P192 clarification

Post by stijn263 »

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 :D
My Maple program just finished, I was really happy my algorithm was correct :-)

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

Re: P192 clarification

Post by sfabriz »

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

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

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

prob-192(best rational approx)

Post by viv_ban »

can any one please confirm the answer for 1 <n <=1000
the answer generated by my program is equal to 610031050010701
thanks in advance
funktio
Posts: 14
Joined: Mon May 19, 2008 6:55 pm
Location: Helsinki, Finland

Re: prob-192(best rational approx)

Post by funktio »

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)

Post by viv_ban »

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)

Post by David F »

I believe so, yes.
Post Reply