20230204, 09:50  #1 
Mar 2017
2^{5} Posts 
Continued fractions to find a squarifying preconditioner?
We're given an integer \(n\), and told that for some squarefree integer \(c\), \(c \cdot n\) is very close to being a perfect square, and \(c \ll \sqrt n\). I don't define "very close" since it's something like n itself having some small uncertainty.
For example, if we're given \(n=33\) then \(c=2\) isn't a good solution since 66 is not close to being a square. \(c=3\) is a great solution, since 99 is very close to 10 squared. \(c=5\) is not good, since 165 is not close to being a square, etc. What are the numeric tools you could use to solve this? Brute force, iterating C=1, C=2, C=3 would work but is inelegant end inefficient for large n. The "close to being a square" means we can't expect it to be exactly a square, so we can't explicitly form C by factoring n to find its nonsquare factors. n's fuzziness also means we can't make some sieve over a range of c, excluding invalid quadradic residues mod 3, 5, 7, 11, etc. It smells like some kind of continued fraction decomposition could spit out a series of increasingly "good" c, but I'm at a loss as how to apply that vague idea in practice. I'd appreciate any suggestions! 
20230205, 00:25  #2  
Jan 2021
California
21A_{16} Posts 
Quote:
Quote:
Defining how you determine closeness may inform you a bit on what tools to consider. 

20230205, 16:27  #3 
Sep 2009
3^{2}·271 Posts 
I'm not sure what you mean by "\(c \ll \sqrt n\)" (my browser doesn't format things properly). But if it means c divides INT(SQRT(n)) then factoring INT(SQRT(n)) would be a good start. Then drawing up a list of squarefree numbers that divide it and trying each of them (assuming there are not too many) to see which gets the best result would be the obvious next step.

20230205, 17:15  #4  
Jan 2021
California
2×269 Posts 
Quote:


20230206, 04:17  #5  
Mar 2017
2^{5} Posts 
Quote:
Here's a better example of what I mean. Think of it as multiplying given n by a small constant c in order to make better and better approximations to a perfect square. Let's look at successive "best" C for an example for (randomly picked) n=51500527 by looking at the deltas from a perfect square and ignoring the C which don't improve the delta from the previous best. You can see the magnitude of the delta decreasing each step. Code:
1 * 51500527 = 7176^2 + 5551 2 * 51500527 = 10149^2  1147 17 * 51500527 = 29589^2 + 38 31522 * 51500527 = 1274127^2  35 40022 * 51500527 = 1435672^2 + 10 304737 * 51500527 = 3961580^2  1 What I want is a procedure or heuristic that says "try c=2, c=17, or c=31522". The table above was computed by exhaustively testing all possible c! Another random example for n= 510006021 shows successively better c multipliers of 1, 9, 14, 53, 4501.... Code:
1 * 510006021 = 22583^2 + 14132 9 * 510006021 = 67750^2  8311 14 * 510006021 = 84499^2 + 3293 53 * 510006021 = 164409^2  168 4501 * 510006021 = 1515103^2  88 145001 * 510006021 = 8599499^2 + 20 266344 * 510006021 = 11654915^2  1 My goal isn't to find the "very lowest residual c" where error becomes smallest, it's to find a small C that gives lower residuals compared to any smaller c. So C=17 in my first example is good, and c=14 or 53 or 4501 in my second example is good. Last fiddled with by mathPuzzles on 20230206 at 04:22 

20230206, 14:03  #6 
Feb 2017
Nowhere
14273_{8} Posts 
You might want to consider dropping your condition that c be squarefree. In your example n= 510006021, c = 9 is among your "good" multipliers.
The question of small c for which c*n is "almost" a square arises WRT Fermat's method of factoring by expressing a number as a difference of two squares. The method can be extended to apply to when the number is the product of two factors, one of which is very close to a small integer multiple of the other. In a letter dated April 7, 1643, Fermat replied to Mersenne regarding the number n=100895598169 which Mersenne had asked him about, and which he had quickly factored. How he accomplished that is not recorded AFAIK. However, as pointed out in a book I read many years ago, 8*n = 898423*(898423 + 1), immediately giving n = 898423*112303. (Of course, here 32*n + 1 is a perfect square.) I note WRT your example n = 51500527 that one of your "good" multipliers, 304737 is fairly close to the ratio 3961579/13 of the two prime factors of n. I also note that the simple continued fraction for sqrt(n) will yield any reasonably good square multipliers  namely, the squares of denominators of convergents. 
20230218, 02:28  #7 
Mar 2016
424_{10} Posts 
A peaceful day for everyone,
I did not understand what the best runtime for continued fraction (https://en.wikipedia.org/wiki/Continued_fraction) is. I know that you could easily use the euclidean algorithm and matrix multiplication in order to transform an irrational number into a rational approximation. But how fast can it be done ? Is there perhaps an implementation in mpfr.h or in another library available ? Thanks in advance if you could clarify these questions. 
20230302, 13:28  #8 
Dec 2022
310_{10} Posts 
It really seems like it ought to work, doesn't it? But I don't believe it can, as I don't see how to express this as a quadratic form (if the number to multiply by were a square, it of course would be).
As your examples suggest, an error of 1 can always be achieved; this is a simple matter of factorisation. An error of +1 can be achieved iff n is a sum of coprime squares, but the multiplier doesn't seem efficiently computable in that case. If the problem is stated as 'find the smallest multiplier such that the proportional error is less than epsilon' (and your original is apparently just a series of those) I have no intuition whatsoever, which means it's probably NPcomplete ;) 
20230303, 14:18  #9  
Feb 2017
Nowhere
13×487 Posts 
Quote:
Then n divides (a*y + b*x)^2 + 1. The multiplier is x^2 + y^2. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Egyptian Fractions  MattcAnderson  Math  0  20201123 03:23 
Fractions 1/m and 1/n  enzocreti  enzocreti  1  20200305 06:33 
a joke about fractions  MattcAnderson  Lounge  1  20170101 14:34 
why continued fractions gives one factor for N=(4m+3)(4n+3)  wsc811  Miscellaneous Math  6  20131129 21:43 
Prime fractions  robert44444uk  Math  14  20080902 17:10 