 mersenneforum.org The new strong (extended) factoring method using the 4-square representation of an integer.
 Register FAQ Search Today's Posts Mark Forums Read  2017-06-21, 21:04   #100
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts Quote:
 Originally Posted by Batalov No. If N can be "tiled" with a^2, b^2, c^2 and d^2, then N = a^2+b^2+c^2+d^2, but not the other way around. 11^2 = 10^2+4^2+2^2+1^2. Can you tile 11x11 with these squares?
no but if you can't it won't give you a factor I bet.   2017-06-21, 23:36   #101
mahbel

Feb 2017
Kitchener, Ontario

22×3×5 Posts Quote:
 Originally Posted by Batalov No. If N can be "tiled" with a^2, b^2, c^2 and d^2, then N = a^2+b^2+c^2+d^2, but not the other way around. 11^2 = 10^2+4^2+2^2+1^2. Can you tile 11x11 with these squares?
the 11x11 square cannot be tiled by (10,4,2,1) squares, simply because if you start with 10x10 square you won't be left with enough space for the other squares.

But I can see that we can get a factor by adding 10+1=11. Finding a factor can be done even with 4-sq reps that cannot tile a square. And that's the whole point of what I said previously.

And in fact, there are two other 4-sq reps that would give a factor (9,6,2,0) and (7,8,2,2). we can see that 9+2=11 and 7+2+2=11 although both of these 2 resp won't tile the 11x11 because 9+6>11 and 7+8>11.

To get a tiling, I suppose we would have to expand 10^2 of the (10,4,2,1) rep as a sum of smaller squares.

Last fiddled with by mahbel on 2017-06-21 at 23:44 Reason: added one example   2017-06-22, 01:35   #102
CRGreathouse

Aug 2006

597910 Posts Quote:
 Originally Posted by Batalov No. If N can be "tiled" with a^2, b^2, c^2 and d^2, then N = a^2+b^2+c^2+d^2, but not the other way around.
Tiling is more restrictive, to be sure. (I wonder what the asymptotics look like here -- for a given composite n, how often is there a rectangle with sides greater than 1 such that the rectangle can be dissected into at most k squares for some fixed k?) But that doesn't mean it couldn't work, just limits how often and how easily.

I don't have good geometric intuition so I'm not sure I have much to contribute here. But aren't there parameterized dissections of rectangles into (fixed numbers of) squares? It might be interesting to see what factorizations they correspond to.   2017-06-22, 12:45   #103
Dr Sardonicus

Feb 2017
Nowhere

22×32×139 Posts Quote:
 Originally Posted by mahbel No, you don't need to "have already factored N". It was done to justify using combinations of non-squares (a,b,c,d) to get a factor.
Nonsense. In both your examples you began with a factorization of N. And in one of them, you resorted to chopping a 6 x 6 square into smaller equal squares to get a tiling. (Of course, to perform this task means you have to factor the side of the square. Oh, joy! Another factoring problem!) In another, you chopped a 4 x 4 square into a bunch of squares, not all equal. And you knew you had to do this only because you knew the rectangle you wanted to tile.

None of this tiling business helps with the actual problem of factoring N, and this thread began with a claim of having a new method for doing that. I have produced examples in which your originally-described method simply cannot work. Your response was, "change the method." But you have not given any reason to justify the notion that combining the squares with their roots has any more chance of finding a factor of N than does trying random numbers. Or even that this approach always works. But I imagine that if someone went to the trouble of finding a counter-example to your "strong extended" method, you would just come up with another ad hoc variation that works on that particular example.

And, since generating random numbers is so much easier than finding representations of N as a sum of four squares, experiment has shown that trying random numbers can find a factor faster than your "method," by many orders of magnitude. Your response to that was an insulting troll.

Sorry, but merely repeating "it works!" no matter how many times, even in the face of contrary facts and evidence, and insulting those who provide such facts and evidence, doesn't go anywhere towards proving it does.

The subject of tiling rectangles with squares has been around for a while. Back in the day, Martin Gardner devoted one of his "Mathematical Games" column to "Squaring the Square." There is even a doctoral thesis on the subject of tiling rectangles with squares here.

Last fiddled with by Dr Sardonicus on 2017-06-22 at 12:53   2017-06-22, 13:07   #104
mahbel

Feb 2017
Kitchener, Ontario

6010 Posts Quote:
 Originally Posted by Dr Sardonicus And, since generating random numbers is so much easier than finding representations of N as a sum of four squares, experiment has shown that trying random numbers can find a factor faster than your "method," by many orders of magnitude. Your response to that was an insulting troll. Sorry, but merely repeating "it works!" no matter how many times, even in the face of contrary facts and evidence, and insulting those who provide such facts and evidence, doesn't go anywhere towards proving it does..
I think you are the one doing all the insulting. Just re-read your comments in case you forgot.

As to using combinations of non-squares (a,b,c,d) to find a factor, I have provided at least 3 examples to show that it works. Instead of commenting on those examples and telling us why they need to be rejected, you continue to ignore those results because it's difficult to argue with numbers when they are correct.

The last example is 11^2= 10^2+4^2+2^2+1^2. Anyone can see that 10+1=11 is a factor. You are the one who is saying 10+1 sometimes makes 11 and sometimes doesn't.

Please give us half a reason why we should reject 10+1=11 as a factor. Then we can all move on to something else.   2017-06-22, 14:44   #105
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts Quote:
 Originally Posted by mahbel I think you are the one doing all the insulting. Just re-read your comments in case you forgot. As to using combinations of non-squares (a,b,c,d) to find a factor, I have provided at least 3 examples to show that it works. Instead of commenting on those examples and telling us why they need to be rejected, you continue to ignore those results because it's difficult to argue with numbers when they are correct. The last example is 11^2= 10^2+4^2+2^2+1^2. Anyone can see that 10+1=11 is a factor. You are the one who is saying 10+1 sometimes makes 11 and sometimes doesn't. Please give us half a reason why we should reject 10+1=11 as a factor. Then we can all move on to something else.
The problem with examples is they only show one case, and not a general case that works constantly for any size N. Also, if we know the factors, then it need not be factored. I do agree that I was hasty a bit with my comparison. What you are basically trying to do is find a rectangle of squares without knowing the dimensions of the rectangle ( or it's equivalent area ones) and hoping to find one side.   2017-06-22, 16:01   #106
CRGreathouse

Aug 2006

3·1,993 Posts Quote:
 Originally Posted by science_man_88 The problem with examples is they only show one case, and not a general case that works constantly for any size N.
Another problem is that the examples used are small, and small numbers are weird. See Guy's papers on the Small Law of Small Numbers.   2017-06-22, 18:30   #107
mahbel

Feb 2017
Kitchener, Ontario

748 Posts Quote:
 Originally Posted by science_man_88 The problem with examples is they only show one case, and not a general case that works constantly for any size N. Also, if we know the factors, then it need not be factored. I do agree that I was hasty a bit with my comparison. What you are basically trying to do is find a rectangle of squares without knowing the dimensions of the rectangle ( or it's equivalent area ones) and hoping to find one side.
yes, you are right. The second part of the quote above is exactly what we are trying to do. And we can't find a factor if we tie our hands behind our back.

We first try to use combinations of squares (a^2,b^2,c^2,d^2), then combinations of non-squares (a,b,c,d) and if we still haven't find a factor, we use a mixture of square and non-squares combinations. I have not experimented with the order, that is which combinations should be first used. I can't tell which one will lead faster to a factor.

If by now, we haven't found a factor, we use the next 4-sq representation and do the same thing.

Last fiddled with by mahbel on 2017-06-22 at 18:46   2017-06-22, 18:44   #108
mahbel

Feb 2017
Kitchener, Ontario

3C16 Posts Quote:
 Originally Posted by CRGreathouse Another problem is that the examples used are small, and small numbers are weird. See Guy's papers on the Small Law of Small Numbers.
I can only agree with the above. The problem will persist even if I were to provide 10^6 examples because the next example, the 10^6 +1, may not work. I realize that the method is not based on a sound theoretical basis (no derivation from first mathematical principles, no theorems, no nothing).

But in more than 18 months of testing, I have never encountered a number, among the small ones that were considered, that cannot be factored by a combination of the 3 combinations (squares, non-squares, and squares + non-squares). But of course, I realize that it's not enough and the numbers tried are small.

Last fiddled with by mahbel on 2017-06-22 at 18:47   2017-06-22, 19:21   #109
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts Quote:
 Originally Posted by mahbel I can only agree with the above. The problem will persist even if I were to provide 10^6 examples because the next example, the 10^6 +1, may not work. I realize that the method is not based on a sound theoretical basis (no derivation from first mathematical principles, no theorems, no nothing). But in more than 18 months of testing, I have never encountered a number, among the small ones that were considered, that cannot be factored by a combination of the 3 combinations (squares, non-squares, and squares + non-squares). But of course, I realize that it's not enough and the numbers tried are small.
that's simply not enough, there are 81 possibilities without repeating variables I laid that out ( including 0 in the set of sums) in post 51 of the thread. so in theory until n>81 if the sums are distinct then they can represent all numbers less than or equal to n. so testing n<=81 will not help because of course in 81 distinct sums there will be at least one that can represent a number in fact given a number less than the number of integer sums considered at least k will be for one number if the number of sums\n = k-1 where \ means floor of division. that's a given using the pigeonhole principle and it's generalizations. edit:and we could probably lift that limit some as we really only care to check if they share a prime divisor at first those are it's simplest divisors in which case if we could prove they could all be consecutive primes then that means our number has to have a divisors below the 80th prime (409, edit2: okay 419 technically if N is odd because 2 can't be a factor)) to succeed ( in the best case). edit3: okay maybe not all that as each one could have multiple prime factors etc. which means you need to get awfully high potentially before it's luck of the draw.

Last fiddled with by science_man_88 on 2017-06-22 at 19:59   2017-06-22, 20:31   #110
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts Quote:
 Originally Posted by science_man_88 that's simply not enough, there are 81 possibilities without repeating variables I laid that out ( including 0 in the set of sums) in post 51 of the thread. so in theory until n>81 if the sums are distinct then they can represent all numbers less than or equal to n. so testing n<=81 will not help because of course in 81 distinct sums there will be at least one that can represent a number in fact given a number less than the number of integer sums considered at least k will be for one number if the number of sums\n = k-1 where \ means floor of division. that's a given using the pigeonhole principle and it's generalizations. edit:and we could probably lift that limit some as we really only care to check if they share a prime divisor at first those are it's simplest divisors in which case if we could prove they could all be consecutive primes then that means our number has to have a divisors below the 80th prime (409, edit2: okay 419 technically if N is odd because 2 can't be a factor)) to succeed ( in the best case). edit3: okay maybe not all that as each one could have multiple prime factors etc. which means you need to get awfully high potentially before it's luck of the draw.
doh before it's not * luck of the draw. my math has the possibility of the first semiprime this may fail for being higher than 544 million because at 8* number of divisors * 80 checks ( though I did the math with 81 including 0 multiple times) means a semiprime which has 4 divisors total that don't divide by 4 ( assuming it's not 4) could have 8*81*number of divisors = 8*81*4= 648*4 -> 23227( prime 2592) ; the nextprime that could possibly be outside of the representations then is 23251; which is only the lowest divisor of a number if it's greater than or equal to 540,609,001 potentially. and proving me wrong without math or fast code ( testing one number a second for example) you will take more than 17 years to disprove/prove it doing them in order potentially. edit: and that's probably even low with my crap math.

Last fiddled with by science_man_88 on 2017-06-22 at 20:37   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post sweety439 sweety439 1250 2021-10-01 12:53 3.14159 Factoring 233 2011-05-15 18:50 ET_ Miscellaneous Math 40 2010-06-06 12:55 1260 Miscellaneous Math 46 2010-05-31 17:37 kpatsak Math 4 2007-10-29 17:53

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

Mon Oct 25 05:18:46 UTC 2021 up 93 days, 23:47, 0 users, load averages: 1.30, 1.13, 1.07