Continued fractions to find a squarifying preconditioner?

[mathPuzzles]

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!

[slandrum]

Originally Posted by mathPuzzles

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.

You don't have to define "very close" but you do have to define how you measure closeness.

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.

Here's the problem - you say 66 is not close to a square, but 66 = 64+2 = 64*1.03, and \(\sqrt 66\) = 8.12, where 99 = 100-1 = 100*.99 and \(\sqrt 99\) is 9.95, obviously 99 is closer to 100 than 66 is to 64 by all of these measures, but it's not clear where the "very close" line is in any of the measures, and in some cases where you are looking for the "closest" out of a set you'll need to be precise in how closeness is defined.

Defining how you determine closeness may inform you a bit on what tools to consider.

[chris2be8]

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

[slandrum]

Originally Posted by chris2be8

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

I took it to mean that c is less than \(\sqrt n\). At least that's what the symbols suggested on my output.

[mathPuzzles]

Originally Posted by slandrum

Here's the problem - you say 66 is not close to a square, but 66 = 64+2 = 64*1.03, and \(\sqrt 66\) = 8.12, where 99 = 100-1 = 100*.99 and \(\sqrt 99\) is 9.95... Defining how you determine closeness may inform you a bit on what tools to consider.

That's my fault for manually making a too-simple vague example which was a poor illustration, thanks for catching my sloppiness!

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.

        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

So here we see that c=2 is a better multiplier than c=1, c=17 is much much better than c=2, next best is all the way at c=31522 and is barely better.

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

        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

To me this just feels like a continued fraction somehow with the jumps in "best" c appearing just like the best rational fraction value appears during a continued fraction expansion.

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.

[Dr Sardonicus]

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.

[bhelmes]

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.

[Andrew Usher]

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 NP-complete ;)

[Dr Sardonicus]

Originally Posted by Andrew Usher

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

If an expression n = a^2 + b^2 as a sum of coprime squares is given, two corresponding multipliers (corresponding to equal and opposite square roots of -1 (mod n)) can be found efficiently by solving a*x - b*y = ±1 using the Euclidean algorithm or simple continued fractions.

Then n divides (a*y + b*x)^2 + 1. The multiplier is x^2 + y^2.