Project Euler Forum

Problem 192 says:

Find the sum of all denominators of the best approximations to √n for the denominator 10¹², 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?

Have you a suggestion?

Edit: I introduced the term "denominator bound", is that better?

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.

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

My solution fits in 64 bit integers. Excepting the denominators themselves, everything's 32 bits.

I must admit that I do not fully understand your solution, daniel

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

Done, posted in the thread.

Don't feel like making a biginter class in C++ so I'm just going to let my program run overnight in Maple

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

902212330695 is correct.

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

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

Tommy137 wrote:902212330695 is correct.

Allright, thank you.
Now I'm 1/99684 done with this problem...

Cheers

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

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

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

can any one please confirm the answer for 1 <n <=1000
the answer generated by my program is equal to 610031050010701
thanks in advance

I get a slightly smaller number.

is the answer to my question = 561480917932597

I believe so, yes.