mersenneforum.org Continued fractions to find a squarifying preconditioner?
 Register FAQ Search Today's Posts Mark Forums Read

 2023-02-04, 09:50 #1 mathPuzzles   Mar 2017 25 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!
2023-02-05, 00:25   #2
slandrum

Jan 2021
California

21A16 Posts

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

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

 2023-02-05, 16:27 #3 chris2be8     Sep 2009 32·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 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.
2023-02-05, 17:15   #4
slandrum

Jan 2021
California

2×269 Posts

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

2023-02-06, 04:17   #5
mathPuzzles

Mar 2017

25 Posts

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

Last fiddled with by mathPuzzles on 2023-02-06 at 04:22

 2023-02-06, 14:03 #6 Dr Sardonicus     Feb 2017 Nowhere 142738 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.
 2023-02-18, 02:28 #7 bhelmes     Mar 2016 42410 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.
 2023-03-02, 13:28 #8 Andrew Usher   Dec 2022 31010 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 NP-complete ;)
2023-03-03, 14:18   #9
Dr Sardonicus

Feb 2017
Nowhere

13×487 Posts

Quote:
 Originally Posted by Andrew Usher 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 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post MattcAnderson Math 0 2020-11-23 03:23 enzocreti enzocreti 1 2020-03-05 06:33 MattcAnderson Lounge 1 2017-01-01 14:34 wsc811 Miscellaneous Math 6 2013-11-29 21:43 robert44444uk Math 14 2008-09-02 17:10

All times are UTC. The time now is 05:49.

Sun Mar 26 05:49:24 UTC 2023 up 220 days, 3:17, 0 users, load averages: 0.88, 0.79, 0.77