mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2017-06-19, 21:10   #78
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

11×461 Posts
Default

Quote:
Originally Posted by mahbel View Post
What right do you have to change the title of a thread started by another user?
See red color of poster's name. = supermod. If you wish to stick around here long enough to continue to reinvent your inefficient and ineffective method, you should strongly consider not picking fights with red folks.

There has been plenty of math shown in this thread for why your method (1) fails, and (2) is slower than trial division. There is nothing left for Batalov to demonstrate mathematically, so he chooses to point out that you're defending utter crap; you don't take the hint, so he's blunter than the rest of them. You should listen to him, really.
VBCurtis is offline   Reply With Quote
Old 2017-06-19, 21:22   #79
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

175B16 Posts
Default

Quote:
Originally Posted by mahbel View Post
You are right, 77 is a special case which is not factored by any of its 4-sq rep. However, if we use combinations of (a,b,c,d) instead of the squares (a^2,b^2,c^2,d^2), then we will be able to factor it.
OK, so here is the extended test. Where the original 'only' counted 7 cases, this one counts 18. (Someone should check that I've included all of them, and that I haven't included any twice.)

Code:
sqrtup(n)=n=ceil(n); if(issquare(n,&n),n,sqrtint(n)+1)
mahbelExtended(n)=my(a2,b2,c2,d,d2,g); for(a=sqrtup(n/4),sqrtint(n), a2=a^2; for(b=sqrtup((n-a2)/3),min(sqrtint(n-a2),a), b2=b^2; for(c=sqrtup((n-a2-b2)/2),min(sqrtint(n-a2-b2),b), c2=c^2; if(issquare(n-a2-b2-c2,&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";
But don't worry, if we find a number this can't factor we can just move to a double-extended test where include combinations like a + b^2 + d. I think that would require 72 tests in total. And if that doesn't work we can always use a triple-extended test which allows nonbinary coefficients, or cubes, or something.

My machine is busy with other work, but feel free to use this code to check for numbers this algorithm cannot factor.
CRGreathouse is offline   Reply With Quote
Old 2017-06-19, 21:31   #80
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

@mahbel one thing you'll find when coding is efficiency is key. Any steps that can be decreased should be. One thing from your original post that still bugs me, is you are considering values that aren't primes multiplied by N. Is there a reason I'm not seeing because you can generate say any value that is a square times N, by multiplying by the square root all of a,b,c,d for N. You'll find a lot of them out ahead of time this works for finding at least a few of those. for example 3^2+5^2+7^2+11^2 = 204 ; 816 = 4*204 = 6^2+10^2+14^2+22^2 so some values of the multiplier you had out front don't really add much new information.

Last fiddled with by science_man_88 on 2017-06-19 at 21:38
science_man_88 is offline   Reply With Quote
Old 2017-06-19, 21:37   #81
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

Quote:
Originally Posted by mahbel View Post
If you have anything to say about the method, do it with math. Or is that too much to ask from you? How about you provide that counterexample yourself instead of waiting for someone else to stumble into one. Is-it because it is too complicated for you?
Serge is one of the computational heavies around here, if he's not computing it it's surely because he doesn't think it's worth his time. There's no question he could code something up (and get big iron to run it!) on if he really wanted to.
CRGreathouse is offline   Reply With Quote
Old 2017-06-19, 21:42   #82
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

140D16 Posts
Default

Quote:
Originally Posted by mahbel View Post
If you have anything to say about the method, do it with math.
You first.
Dr Sardonicus is online now   Reply With Quote
Old 2017-06-19, 21:50   #83
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
You first.
Actually I think you're the only one who has used real math in this thread so far, in your analysis (post #72) of the failure of the original algorithm. I just used cheap heuristics and decent algorithms.
CRGreathouse is offline   Reply With Quote
Old 2017-06-19, 23:44   #84
mahbel
 
"mahfoud belhadj"
Feb 2017
Kitchener, Ontario

22×3×5 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
@mahbel one thing you'll find when coding is efficiency is key. Any steps that can be decreased should be. One thing from your original post that still bugs me, is you are considering values that aren't primes multiplied by N. Is there a reason I'm not seeing because you can generate say any value that is a square times N, by multiplying by the square root all of a,b,c,d for N. You'll find a lot of them out ahead of time this works for finding at least a few of those. for example 3^2+5^2+7^2+11^2 = 204 ; 816 = 4*204 = 6^2+10^2+14^2+22^2 so some values of the multiplier you had out front don't really add much new information.
You are asking about why I used a multiplier. I did some testing and found that some multipliers increase the number of good representations ( the ones that provide a factor(s)). If you use N=7*13=91, you get 2 good reps out a total of 8 reps. If you use 2N=2*7*13, you get about the same, slightly bigger 5 out of 17. If you use 3N, you get 12 good out of a total of 21 reps. Here you really see what increasing the value of the multiplier does. If you use 6N, you get 52 out of 63 or 82.5% of good reps. The problem with the multiplier is I couldn't figure out a general rule. So the same multiplier for one number N will not necessarily produce the same result for a different number M. I stuck with 2N more by habit than by anything else.
mahbel is offline   Reply With Quote
Old 2017-06-19, 23:49   #85
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

Honestly I think it's pretty hard to decide what multipliers are useful in general. The OLF paper tries to motivate the choice with some theory, I think, but ends up choosing a multiplier based on numerical experiments IIRC. Maybe some people know more -- Silverman, likely, and a number of experts we have on the forum -- but there's a lot of voodoo and trial-and-error.
CRGreathouse is offline   Reply With Quote
Old 2017-06-20, 00:09   #86
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
Honestly I think it's pretty hard to decide what multipliers are useful in general. The OLF paper tries to motivate the choice with some theory, I think, but ends up choosing a multiplier based on numerical experiments IIRC. Maybe some people know more -- Silverman, likely, and a number of experts we have on the forum -- but there's a lot of voodoo and trial-and-error.
my main point was that if you have a representation for N you can make that into a representation for r^2 N of (ra,rb,rc,rd) and same happens to other multiplies that divide by squares at least some of their representations rely on representations of earlier multipliers.

so for example 612=12*51 and has 4 representations coming from 3*51=153 multiplying the bases by 2.

Last fiddled with by science_man_88 on 2017-06-20 at 00:10
science_man_88 is offline   Reply With Quote
Old 2017-06-20, 00:12   #87
mahbel
 
"mahfoud belhadj"
Feb 2017
Kitchener, Ontario

1111002 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
my main point was that if you have a representation for N you can make that into a representation for r^2 N of (ra,rb,rc,rd) and same happens to other multiplies that divide by squares at least some of their representations rely on representations of earlier multipliers.

so for example 612=12*51 and has 4 representations coming from 3*51=153 multiplying the bases by 2.
I never considered square multipliers. I don't really see the point.
mahbel is offline   Reply With Quote
Old 2017-06-20, 00:15   #88
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by mahbel View Post
I never considered square multipliers. I don't really see the point.
it doesn't just affect squares any multiplier that is not square-free is affected. also 4 in your 4p case is a square.

Last fiddled with by science_man_88 on 2017-06-20 at 00:27
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A Sierpinski/Riesel-like problem sweety439 sweety439 1250 2021-10-01 12:53
Another factoring method rides the bus 3.14159 Factoring 233 2011-05-15 18:50
Square numbers and binary representation ET_ Miscellaneous Math 40 2010-06-06 12:55
Is this a feasible factoring method? 1260 Miscellaneous Math 46 2010-05-31 17:37
Representation of integer as sum of squares kpatsak Math 4 2007-10-29 17:53

All times are UTC. The time now is 17:25.


Sat Dec 4 17:25:57 UTC 2021 up 134 days, 11:54, 1 user, load averages: 1.13, 1.34, 1.32

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.