Problem 192

[JohnMorris]

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?

[daniel.is.fischer]

Have you a suggestion?

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

[Georg]

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]

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]

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

[Tommy137]

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

[daniel.is.fischer]

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

Done, posted in the thread.

[stijn263]

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

[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

[Tommy137]

902212330695 is correct.

[daniel.is.fischer]

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

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

[sfabriz]

902212330695 is correct.

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

Cheers

[Tommy137]

902212330695 is correct.

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

Cheers

It seems you solved it though

[stijn263]

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]

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]

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]

I get a slightly smaller number.

[viv_ban]

is the answer to my question = 561480917932597

[David F]

I believe so, yes.