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-25, 18:44   #166
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

2×1,087 Posts

Quote:
 Originally Posted by CRGreathouse I don't know what m is or why it is needed. But couldn't you just scale the grid by a factor of m and use smaller squares?
It's a matter of formulating the problem that needs to be solved. One way is to set the rectangle with integer side m and unknown side x equal to the 4 square sums. Like I said it's not sufficient constraints for factoring. But that's the first equation. You need more to ensure integer domain solutions for x.
It is not theoretically impossible but very impractical.

Last fiddled with by a1call on 2017-06-25 at 19:03

2017-06-25, 19:43   #167
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

2·1,087 Posts

Quote:
 Originally Posted by CRGreathouse I don't know what m is or why it is needed. But couldn't you just scale the grid by a factor of m and use smaller squares?
Now that I think about it, that is very clever. That indeed is a valid factorization method (much simpler applied algebraically than geometrically).

21/9 -> 63/9 -> 21/3.

Of course unless the scale has a common factor grater than 1 with m, then it's not of much use.

As a measure of potential complexity and extra numbers of steps involved in geometrical solutions versus algebraical solutions, consider the solution I came up with for 5 inscribed circles in a circle here:

vs. its algebraic solution:

Code:
The trigonometric formula for the radius r1 of n equal, tangent and inscribed circles inside a larger circle of radius r2 is:
r1 = (r2 sin (180/n))/(1+sin (180/n))
Its worth pointing out that I settled to providing a link to drawing pentagons rather than including it in the instructions.

Last fiddled with by a1call on 2017-06-25 at 19:59

 2017-06-25, 20:36 #168 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2·1,087 Posts This might be one theoretical use of the concept: Code: theExp = 5;\\larger integers will enlarge random n # \\\ primorial(n)= { my(thePrimorial=1); forprime(p=2,n,thePrimorial=thePrimorial*p); return (thePrimorial); } \\\ n=nextprime(random(19^theExp ))*nextprime(random(19^theExp )) factor(n) ## pr= primorial(sqrtint(n)); ## { s= n/ pr; print("** ",numerator(s)) } ## Code: (16:31) gp > n=nextprime(random(19^theExp ))*nextprime(random(19^theExp )) %10 = 5452058249203 (16:31) gp > factor(n) %11 = [2236807 1] [2437429 1] (16:31) gp > ## *** last result computed in 0 ms. (16:31) gp > (16:31) gp > pr= primorial(sqrtint(n)); time = 7,376 ms. (16:31) gp > ## *** last result computed in 7,376 ms. (16:31) gp > { s= n/ pr; print("** ",numerator(s)) } ** 2437429 (16:31) gp > ## *** last result computed in 0 ms. (16:31) gp >
 2017-06-25, 22:06 #169 CRGreathouse     Aug 2006 3·1,993 Posts As a sidenote, might I suggest Code: n=randomprime([2,19^5])*randomprime([2,19^5]); rather than Code: theExp = 5;\\larger integers will enlarge random n n=nextprime(random(19^theExp ))*nextprime(random(19^theExp )) ? That was you get a uniform selection* and it's a little easier to see what's going on. Also, you should probably increase the lower bound -- maybe randomprime([1e5, 3e5]) would be better. * Consider that, with theExp = 5, 2010881 is chosen 148 times more often than 3 and 74 times more often than 2010973.
 2017-06-25, 22:29 #170 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 87E16 Posts Cool. I did not know that, Thank you.
 2017-06-25, 23:07 #171 CRGreathouse     Aug 2006 3·1,993 Posts I posted a very fiddly program Code: rsp(len)=my(mn=10^(len-1),mx=10^len-1,p=randomprime([sqrtup(mn/2),sqrtint(mx)]),q=randomprime([ceil(mn/p),mx\p])); p*q; earlier which, given a number of digits, finds a semiprime pq with that number of digits such that p <= q < 2p. It's not uniform but good enough for these purposes. Last fiddled with by CRGreathouse on 2017-06-25 at 23:07
 2017-06-25, 23:20 #172 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 41768 Posts My version doesn't seem to recognize sqrtup() works fine with ceil(sqrt(mn/2)), though. Cool code, thank you. Adding it to my library under semiprimes.
2017-06-26, 00:04   #173
CRGreathouse

Aug 2006

597910 Posts

Quote:
 Originally Posted by a1call My version doesn't seem to recognize sqrtup() works fine with ceil(sqrt(mn/2)), though.
sqrtup is a function I defined to avoid the floating-point roundoff of that approach. I give the code a few times in this thread but forgot to include it with that snippet, here it is:
Code:
sqrtup(n)=n=ceil(n); if(issquare(n,&n),n,sqrtint(n)+1);
Quote:
 Originally Posted by a1call Cool code, thank you. Adding it to my library under semiprimes.

Last fiddled with by CRGreathouse on 2017-06-26 at 00:05

 2017-06-26, 00:17 #174 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2·1,087 Posts Got it. Thank you very much.
2017-06-27, 18:50   #175
mahbel

Feb 2017
Kitchener, Ontario

22·3·5 Posts

Quote:
 Originally Posted by CRGreathouse In fairness I mentioned this on page 3 and showed how much faster it was. So, the takeaways:These numbers are really small. I wasn't able to go much higher because the methods were too slow. Overhead matters a lot. My stupid method is twice as fast as Dr Sardonicus's stupid method just because mine does less work and so it spends more time searching. Contrary to my expectations, the extensions helped a lot. I think that's because the algorithm I'm using for four-square representations is slow and the more checks you do inside of each one you find, the better (because each one is expensive to find). It should surprise no one that all methods were much slower than trial division, which is much slower than a real method.
It turned out that one 4-sq representation can be transformed into another simply by expanding the squares in the first one and re-arranging them to create new 4-sq representations. It can be shown that for N=7*13=91, the first 4-sq rep (5,5,5,4) can be transformed into any other representation.

And in fact, if one used the expanded squares of a given representation, one can find more factors. Take the example of the first 4-sq rep (5,5,5,4).
5^2=4^2+2^2+2^2+1^2
5^2=4^2+2^2+2^2+1^2
5^2=4^2+2^2+2^2+1^2
4^2=2^2+2^2+2^2+2^2

combining these squares, it is easy to see that:
4^2 + 2^2 + 1^2 = 21 = 3*7
2^2 + 2^2 + 2^2 + 1^1 = 13
2^2 + 1^2 + 1^2 + 1^2 = 7
4^2 + 2^2 + 2^2 + 2^2 = 28 = 4*7
4^2 + 4^2 + 1^2 + 1^2 + 1^2 = 35 = 5*7
....

2017-06-27, 21:40   #176
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts

Quote:
 Originally Posted by mahbel [/LIST]It turned out that one 4-sq representation can be transformed into another simply by expanding the squares in the first one and re-arranging them to create new 4-sq representations. It can be shown that for N=7*13=91, the first 4-sq rep (5,5,5,4) can be transformed into any other representation. And in fact, if one used the expanded squares of a given representation, one can find more factors. Take the example of the first 4-sq rep (5,5,5,4). 5^2=4^2+2^2+2^2+1^2 5^2=4^2+2^2+2^2+1^2 5^2=4^2+2^2+2^2+1^2 4^2=2^2+2^2+2^2+2^2 combining these squares, it is easy to see that: 4^2 + 2^2 + 1^2 = 21 = 3*7 2^2 + 2^2 + 2^2 + 1^1 = 13 2^2 + 1^2 + 1^2 + 1^2 = 7 4^2 + 2^2 + 2^2 + 2^2 = 28 = 4*7 4^2 + 4^2 + 1^2 + 1^2 + 1^2 = 35 = 5*7 ....
you can break down almost any partition that way though: partitions of 9:
9
8,1
7,2
7,1,1
6,3
6,2,1
6,1,1,1
5,4
5,3,1
5,2,2
5,2,1,1
5,1,1,1,1
4,5
4,4,1
4,3,2
4,3,1,1
4,2,1,1,1
4,1,1,1,1
3,6
3,5,1
3,4,2
3,4,1,1
3,3,1,1,1
3,2,1,1,1,1
3,1,1,1,1,1,1
3,3,3
3,3,2,1
3,3,1,1,1
3,2,1,1,1,1
3,1,1,1,1,1,1
...

all the red are partitions of another partition. some of these are also duplicates of earlier ones 3,4,2 and 4,3,2 and 2,3,4 for example ( there's actually 6 possible ways to rearrange these but that's also why you can cut the work back searching for the square sums because there are 16 with sign changes, each having 24 orderings.

 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 10:32.

Wed Dec 1 10:32:18 UTC 2021 up 131 days, 5:01, 1 user, load averages: 0.88, 1.08, 1.12