1
$\begingroup$

Given a very large integer $n$, I wish to find integer multipliers $m$ such that the product is nearly a perfect square. Ideally this should be easy to compute and output a series of improved approximates. We'll define a quality measure as "nearly a perfect square" as minimizing the quantity $\sqrt{nm} - \left \lfloor\sqrt{nm}\right \rfloor$.

As an example with a small $n=87654321$ a useful series of better and better $m$ values can be brute force evaluated by exhaustively testing $m$ values starting at 1. Notice how the fractional remainder of the square root decreases monotonically as it finds better multipliers:

87654321 * 1       =      9362.3886375219 ^2
87654321 * 3       =     16216.1328003936 ^2  
87654321 * 6       =     22933.0749355598 ^2  
87654321 * 26      =     47739.0023565638 ^2
87654321 * 249     =    147736.0007885688 ^2
87654321 * 2766    =    492394.0006600405 ^2 
87654321 * 3469    =    551428.0003309589 ^2 
87654321 * 5751    =    710000.0000500000 ^2 
87654321 * 15967   =   1183037.0000160604 ^2
87654321 * 44374   =   1972200.0000136902 ^2
87654321 * 156685  =   3705957.0000048568 ^2
87654321 * 392125  =   5862717.0000030706 ^2
87654321 * 790738  =   8325359.0000010207 ^2
87654321 * 1555754 =  11677695.0000003850 ^2
87654321 * 1856354 =  12756075.0000003520 ^2

My question is how to generate this, or a similar, series of "good" $m$ values. I suspect the answer has to do with a continued fraction representation of $\sqrt n$ but I have had no luck turning that hunch into a working method.

An answer I'm not looking for is solving for the smallest $m$ that produces a perfect square. That method is to completely factor $n$, and forming $m$ as a product of all of the factors of $n$ with odd multiplicity. That's a great result but factoring $n$ is impractical for very large (hundreds of digits) values of $n$.

Thanks for help with this fun puzzle!

$\endgroup$
0
$\begingroup$

In PARI/GP you can find a good approximation to the $\sqrt{n}$. Sample code:

? r=bestappr(s=sqrt(n=87654321),10^10);
? print(r," ",frac((d=denominator(r))*s+.5)-.5," ",s*d)
11290906936405/1205985713 -6.97906177E-11  11290906936404.99999999993021
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.