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?Find the sum of all denominators of the best approximations to âˆšn for the denominator 10^{12}, where n is not a perfect square and 1 < n [le] 100000.
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.

 Posts: 64
 Joined: Sun Dec 23, 2007 6:38 am
P192 clarification
Problem 192 says:
 daniel.is.fischer
 Posts: 2400
 Joined: Sun Sep 02, 2007 10:15 pm
 Location: Bremen, Germany
Re: P192 clarification
Have you a suggestion?
Edit: I introduced the term "denominator bound", is that better?
Edit: I introduced the term "denominator bound", is that better?
Il faut respecter la montagne  c'est pourquoi les gypaètes sont là.
Re: P192 clarification
I had no problem to understand it after your correction, when I read P192 for the first time.daniel.is.fischer wrote:Edit: I introduced the term "denominator bound", is that better?
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 10: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ètes sont là.
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 10:15 pm
 Location: Bremen, Germany
Re: P192 clarification
I'll explain. Might take a moment, though.
Done, posted in the thread.
Done, posted in the thread.
Il faut respecter la montagne  c'est pourquoi les gypaètes sont là.
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
Re: P192 clarification
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:
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
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)
Cheers,
sfabriz
Re: P192 clarification
902212330695 is correct.
 daniel.is.fischer
 Posts: 2400
 Joined: Sun Sep 02, 2007 10:15 pm
 Location: Bremen, Germany
Re: P192 clarification
Ever thought of using Java? Or GMP? But you don't need bignums, anywaystijn263 wrote:Don't feel like making a biginter class in C++ so I'm just going to let my program run overnight in Maple
Il faut respecter la montagne  c'est pourquoi les gypaètes sont là.
 rayfil
 Administrator
 Posts: 1403
 Joined: Sun Mar 26, 2006 4:30 am
 Location: Ontario, Canada
 Contact:
Re: P192 clarification
For those following this thread and who may not yet be aware of it, double precision floats (often referred as 64bit 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.64 bit integers and/or double precision floats ?
In order to have 64bit precision with floats, one needs to use extended double precision, i.e. 80bit 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.
Re: P192 clarification
Allright, thank you.Tommy137 wrote:902212330695 is correct.
Now I'm 1/99684 done with this problem...
Cheers
Re: P192 clarification
It seems you solved it thoughsfabriz wrote:Allright, thank you.Tommy137 wrote:902212330695 is correct.
Now I'm 1/99684 done with this problem...
Cheers
Re: P192 clarification
My Maple program just finished, I was really happy my algorithm was correctdaniel.is.fischer wrote:Ever thought of using Java? Or GMP? But you don't need bignums, anywaystijn263 wrote:Don't feel like making a biginter class in C++ so I'm just going to let my program run overnight in Maple
However it seems almost all solutions use bignums..
Re: P192 clarification
Yep, my algo was correct, but I had 50 digits precision and it turned out they weren't enough. 60 have been good.Tommy137 wrote:It seems you solved it thoughsfabriz wrote:Allright, thank you.Tommy137 wrote:902212330695 is correct.
Now I'm 1/99684 done with this problem...
Cheers
Cheers
prob192(best rational approx)
can any one please confirm the answer for 1 <n <=1000
the answer generated by my program is equal to 610031050010701
thanks in advance
the answer generated by my program is equal to 610031050010701
thanks in advance
Re: prob192(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}<>
32+95*rand,$_$"or$.ne$_[$"%2?$"1:$"]&&$"++for++$..$";print}<>
Re: prob192(best rational approx)
is the answer to my question = 561480917932597
Re: prob192(best rational approx)
I believe so, yes.