20170624, 22:02  #155  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
Quote:
etc. I still don't see how you get 127 if you use n things for each part of the sum a sum of 4 things with n each will allow n^4 which 127 does not fit if you allow. yes I I know there's overlap I also know that some sums as squares aren't worth looking at for example for N=4 we have: 2^2+0^2+0^2+0^2 1^2+1^2+1^2+1^2 as well as these times 1 for all (a,b,c,d) (b,c,d,a) etc. some which use all negative numbers. it wasn't specified these wouldn't be used. 

20170624, 23:37  #156  
Feb 2017
Nowhere
5125_{10} Posts 
Quote:
Of course, not all of a, b, c, and d need be different. And even if they are, not all the sums need be different. 

20170625, 00:42  #157  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3×5×641 Posts 
Quote:
The next beautiful enhancement is to drop the requirement that a^2 + b^2 + c^2 + d^2 is close to N. And then again, what is 'close' anyway? I think 17 and 998651 are reasonably close, at least from where I sit (which is at 150290digit numbers). And yet the next enhancement (because now the a^2 + b^2 + c^2 + d^2 can be equal to anything) is to restate: "Take any random a, b, c, d of size of sqrt(N), then do gcd(N, all linear combinations of {a, b, c, d and a^2, b^2, c^2, d^2} ). Repeat N times if needed. I guarantee that you will factor N." Scout's honor! In fact you will factor N faster, because you will not be uselessly check if a^2 + b^2 + c^2 + d^2 is equal (or close) to N. 

20170625, 00:50  #158 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
2×23×137 Posts 
Long ago in this thread it was already apparent that using a^2 + b^2 + c^2 + d^2 = N fails the sufficiency test. And now it appears that using a^2 + b^2 + c^2 + d^2 = N also fails the necessity test.
Yay. So after all the posts here we can can finally ignore the big distraction about bothering to test for a^2 + b^2 + c^2 + d^2 = N and instead just use a bunch of random numbers. Conclusion at last. End of thread. Last fiddled with by retina on 20170625 at 00:51 
20170625, 02:56  #159  
Aug 2006
3×1,993 Posts 
Quote:
Quote:
Code:
scattergun(n)=my(s=sqrtint(n),a2,b2,c2,d2,g); for(a=s\2,n, a2=a^2; for(b=a,s, b2=b^2; for(c=b,s, c2=c^2; for(d=c,s, g=gcd(n,a); if(g>1, return(g)); g=gcd(n,b); if(g>1, return(g)); g=gcd(n,c); if(g>1, return(g)); g=gcd(n,d); if(g>1, return(g)); g=gcd(n,a2+b2); if(g>1 && g<n, return(g)); g=gcd(n,a2+c2); if(g>1 && g<n, return(g)); d2=d^2; g=gcd(n,a2+d2); if(g>1 && g<n, return(g)); g=gcd(n,a+b); if(g>1 && g<n, return(g)); g=gcd(n,a+c); if(g>1 && g<n, return(g)); g=gcd(n,a+d); if(g>1 && g<n, return(g)); g=gcd(n,b+c); if(g>1 && g<n, return(g)); g=gcd(n,b+d); if(g>1 && g<n, return(g)); g=gcd(n,c+d); if(g>1 && g<n, return(g)); g=gcd(n,a+b+c); if(g>1 && g<n, return(g)); g=gcd(n,a+b+d); if(g>1 && g<n, return(g)); g=gcd(n,a+c+d); if(g>1 && g<n, return(g)); g=gcd(n,b+c+d); if(g>1 && g<n, return(g)); g=gcd(n,a+b+c+d); if(g>1 && g<n, return(g)))))); "could not factor"; Code:
factorblind(n)=my(s=(sqrtint(n)3)\2,r); while(n%(r=2*random(s)+3),); r; sqrtup(n)=n=ceil(n); if(issquare(n,&n),n,sqrtint(n)+1); mahbel(n)=my(a2,b2,c2,d,d2,g); for(a=sqrtup(n/4),sqrtint(n), a2=a^2; for(b=sqrtup((na2)/3),min(sqrtint(na2),a), b2=b^2; for(c=sqrtup((na2b2)/2),min(sqrtint(na2b2),b), c2=c^2; if(issquare(na2b2c2,&d)&&c>=d, d2=d^2; g=gcd(n,a); if(g>1 && g<n, return(g)); g=gcd(n,b); if(g>1 && g<n, return(g)); g=gcd(n,c); if(g>1 && g<n, return(g)); g=gcd(n,d); if(g>1 && g<n, return(g)); g=gcd(n,a2+b2); if(g>1 && g<n, return(g)); g=gcd(n,a2+c2); if(g>1 && g<n, return(g)); g=gcd(n,a2+d2); if(g>1 && g<n, return(g)))))); "could not factor"; mahbelExtended(n)=my(a2,b2,c2,d,d2,g); for(a=sqrtup(n/4),sqrtint(n), a2=a^2; for(b=sqrtup((na2)/3),min(sqrtint(na2),a), b2=b^2; for(c=sqrtup((na2b2)/2),min(sqrtint(na2b2),b), c2=c^2; if(issquare(na2b2c2,&d)&&c>=d, d2=d^2; g=gcd(n,a); if(g>1 && g<n, return(g)); g=gcd(n,b); if(g>1 && g<n, return(g)); g=gcd(n,c); if(g>1 && g<n, return(g)); g=gcd(n,d); if(g>1 && g<n, return(g)); g=gcd(n,a2+b2); if(g>1 && g<n, return(g)); g=gcd(n,a2+c2); if(g>1 && g<n, return(g)); g=gcd(n,a2+d2); if(g>1 && g<n, return(g)); g=gcd(n,a+b); if(g>1 && g<n, return(g)); g=gcd(n,a+c); if(g>1 && g<n, return(g)); g=gcd(n,a+d); if(g>1 && g<n, return(g)); g=gcd(n,b+c); if(g>1 && g<n, return(g)); g=gcd(n,b+d); if(g>1 && g<n, return(g)); g=gcd(n,c+d); if(g>1 && g<n, return(g)); g=gcd(n,a+b+c); if(g>1 && g<n, return(g)); g=gcd(n,a+b+d); if(g>1 && g<n, return(g)); g=gcd(n,a+c+d); if(g>1 && g<n, return(g)); g=gcd(n,b+c+d); if(g>1 && g<n, return(g)); g=gcd(n,a+b+c+d); if(g>1 && g<n, return(g)))))); "could not factor"; mahbelDoubleExtended(n)=my(a2,b2,c2,d,d2,g); for(a=sqrtup(n/4),sqrtint(n), a2=a^2; for(b=sqrtup((na2)/3),min(sqrtint(na2),a), b2=b^2; for(c=sqrtup((na2b2)/2),min(sqrtint(na2b2),b), c2=c^2; if(issquare(na2b2c2,&d)&&c>=d, d2=d^2; g=gcd(n,a); if(g>1, return(g));g=gcd(n,b); if(g>1, return(g));g=gcd(n,c); if(g>1, return(g));g=gcd(n,d); if(g>1, return(g));g=gcd(n,a2+b2); if(g>1 && g<n, return(g));g=gcd(n,a2+c2); if(g>1 && g<n, return(g));g=gcd(n,a2+d2); if(g>1 && g<n, return(g));g=gcd(n,c+d); if(g>1 && g<n, return(g));g=gcd(n,c+d2); if(g>1 && g<n, return(g));g=gcd(n,c2+d); if(g>1 && g<n, return(g));g=gcd(n,b+d); if(g>1 && g<n, return(g));g=gcd(n,b+d2); if(g>1 && g<n, return(g));g=gcd(n,b+c); if(g>1 && g<n, return(g));g=gcd(n,b+c+d); if(g>1 && g<n, return(g));g=gcd(n,b+c+d2); if(g>1 && g<n, return(g));g=gcd(n,b+c2); if(g>1 && g<n, return(g));g=gcd(n,b+c2+d); if(g>1 && g<n, return(g));g=gcd(n,a2+b2b); if(g>1 && g<n, return(g));g=gcd(n,b2+d); if(g>1 && g<n, return(g));g=gcd(n,b2+c); if(g>1 && g<n, return(g));g=gcd(n,b2+c+d); if(g>1 && g<n, return(g));g=gcd(n,a2+c2c); if(g>1 && g<n, return(g));g=gcd(n,a2+d2d); if(g>1 && g<n, return(g));g=gcd(n,a+d); if(g>1 && g<n, return(g));g=gcd(n,a+d2); if(g>1 && g<n, return(g));g=gcd(n,a+c); if(g>1 && g<n, return(g));g=gcd(n,a+c+d); if(g>1 && g<n, return(g));g=gcd(n,a+c+d2); if(g>1 && g<n, return(g));g=gcd(n,a+c2); if(g>1 && g<n, return(g));g=gcd(n,a+c2+d); if(g>1 && g<n, return(g));g=gcd(n,a2a+b2); if(g>1 && g<n, return(g));g=gcd(n,a+b); if(g>1 && g<n, return(g));g=gcd(n,a+b+d); if(g>1 && g<n, return(g));g=gcd(n,a+b+d2); if(g>1 && g<n, return(g));g=gcd(n,a+b+c); if(g>1 && g<n, return(g));g=gcd(n,a+b+c+d); if(g>1 && g<n, return(g));g=gcd(n,a+b+c+d2); if(g>1 && g<n, return(g));g=gcd(n,a+b+c2); if(g>1 && g<n, return(g));g=gcd(n,a+b+c2+d); if(g>1 && g<n, return(g));g=gcd(n,a2a+b2b); if(g>1 && g<n, return(g));g=gcd(n,a+b2); if(g>1 && g<n, return(g));g=gcd(n,a+b2+d); if(g>1 && g<n, return(g));g=gcd(n,a2a+c2); if(g>1 && g<n, return(g));g=gcd(n,a+b2+c); if(g>1 && g<n, return(g));g=gcd(n,a+b2+c+d); if(g>1 && g<n, return(g));g=gcd(n,a2a+c2c); if(g>1 && g<n, return(g));g=gcd(n,a2a+d2); if(g>1 && g<n, return(g));g=gcd(n,a2a+d2d); if(g>1 && g<n, return(g));g=gcd(n,a2a); if(g>1 && g<n, return(g));g=gcd(n,a2+d); if(g>1 && g<n, return(g));g=gcd(n,a2+c); if(g>1 && g<n, return(g));g=gcd(n,a2+c+d); if(g>1 && g<n, return(g));g=gcd(n,b2+c2c); if(g>1 && g<n, return(g));g=gcd(n,b2+d2d); if(g>1 && g<n, return(g));g=gcd(n,a2+b); if(g>1 && g<n, return(g));g=gcd(n,a2+b+d); if(g>1 && g<n, return(g));g=gcd(n,b2b+c2); if(g>1 && g<n, return(g));g=gcd(n,a2+b+c); if(g>1 && g<n, return(g));g=gcd(n,a2+b+c+d); if(g>1 && g<n, return(g));g=gcd(n,b2b+c2c); if(g>1 && g<n, return(g));g=gcd(n,b2b+d2); if(g>1 && g<n, return(g));g=gcd(n,b2b+d2d); if(g>1 && g<n, return(g));g=gcd(n,b2b); if(g>1 && g<n, return(g));g=gcd(n,c2+d2d); if(g>1 && g<n, return(g));g=gcd(n,c2c+d2); if(g>1 && g<n, return(g));g=gcd(n,c2c+d2d); if(g>1 && g<n, return(g));g=gcd(n,c2c); if(g>1 && g<n, return(g));g=gcd(n,d2d); if(g>1 && g<n, return(g)))))); "could not factor"; Code:
rsp(len)=my(mn=10^(len1),mx=10^len1,p=randomprime([sqrtup(mn/2),sqrtint(mx)]),q=randomprime([ceil(mn/p),mx\p])); p*q; trialDivision(n)=forprime(p=2,sqrtint(n), if(n%p==0, return(p))); n; gpf(n)=my(f=factor(n)[,1]); f[#f]; test(len,trials,methods)=my(v=vector(trials,i,rsp(len)),t); for(i=1,#methods, gettime(); print1("Method #"i" factored "sum(j=1,#v,t=methods[i](v[j]); type(t)=="t_INT" && t>1 && t<v[j] && v[j]%t==0)); print(" "len"digit numbers in "gettime()" ms.")) test(9, 10, [gpf, trialDivision, factorblind, scattergun, mahbelDoubleExtended, mahbelExtended, mahbel]) PARI's internal algorithms factored 10 9digit numbers in 0 ms. Trial division factored 10 9digit numbers in 4 ms. Guessing random factors (factorblind) factored 10 9digit numbers in 52 ms. Searching nearby squares and nonsquares (Dr Sardonicus's scattergun) factored 10 9digit numbers in 120 ms. Searching squares, nonsquares, and their combinations (mahbel's double extended method) factored 10 9digit numbers in 12677 ms. Searching squares and nonsquares (mahbel's extended method) factored 10 9digit numbers in 94905 ms. Searching squares (mahbel's method) factored 10 9digit numbers in 268852 ms. So, the takeaways:


20170625, 06:18  #160 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
2×23×137 Posts 

20170625, 06:22  #161  
Aug 2006
175B_{16} Posts 
Quote:
I freely admit, as I have each time performance was mentioned, that the comparison would look less bad if I had a faster method for finding foursquare representations. But I think that even if they were already in the L1 cache the speed would be inferior to a properlycoded trial division, let alone Pollard rho. 

20170625, 07:04  #162  
Romulan Interpreter
"name field"
Jun 2011
Thailand
2^{4}·613 Posts 
Quote:
I still don't understand why you say "close to N", any sum will do it (edit whoops, Serge was faster, as usual...) Last fiddled with by LaurV on 20170625 at 07:06 

20170625, 13:07  #163  
Feb 2017
Nowhere
5125_{10} Posts 
Quote:
It might even give the checking of random numbers up to sqrt(N) a run for its money 

20170625, 15:58  #164  
"Rashid Naimi"
Oct 2015
Remote to Here/There
2·1,087 Posts 
Finding a geometric solution to forming a rectangle out of any given 4 squares is possible in the classical sense of using a compass and a straightedge.
It's algebraic equivalent its: x = (a^2 + b^2 + c^2 + d^2) / m x is a constructible number. However it does not have to be an integer for integers a,b,c,d,m. So it cannot be a basis for factorization without other constraints which ensue integerness. https://en.m.wikipedia.org/wiki/Constructible_number ETA Quote:
Last fiddled with by a1call on 20170625 at 16:34 

20170625, 18:02  #165  
Aug 2006
3×1,993 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
A Sierpinski/Riesellike problem  sweety439  sweety439  1250  20211001 12:53 
Another factoring method rides the bus  3.14159  Factoring  233  20110515 18:50 
Square numbers and binary representation  ET_  Miscellaneous Math  40  20100606 12:55 
Is this a feasible factoring method?  1260  Miscellaneous Math  46  20100531 17:37 
Representation of integer as sum of squares  kpatsak  Math  4  20071029 17:53 