View Single Post
Old 2010-11-03, 17:25   #7
Account Deleted
Mini-Geek's Avatar
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

426710 Posts

Originally Posted by science_man_88 View Post
if we say we need at least 1 factor of the same type mod 6 then we only have to check when 4n+1 or 4n match up with 3x+1 and we should find possible factors k= 1,13,etc. because 4n+1 meets 3x+1 every fourth value and every 3rd value greater than index =2 for 4n this limits it to at most if we can figure on thing out i could narrow it down to finding factors on one or the other k list for mod 8 but anyways.
We don't always need at least 1 factor of the same type mod 6, and on large numbers we have no clue how many other factors there are. Consider a number that is 1 mod 6. It must have an even number of factors that are -1 mod 6, but that includes 0, 2, 4, etc. And it can have any number of factors that are 1 mod 6. It really doesn't help. It could have two factors that are -1 mod 6 and none that are 1 mod 6. Or 0 factors that are -1 mod 6 and 1 that is 1 mod 6 (a.k.a. it's prime), or anything else.
Yes, excluding k's that make 2kp+1 not 1 or 5 mod 6 narrows down the list. It removes a great deal of candidates, but it does so by removing all composites with 2 or 3 as a factor. You can find the same thing by just checking each 2kp+1 to see if it has 3 as a factor (since the form is 2kp+1, they're all odd, 2 can never be a factor). The question, then, is: Is it better to figure out which k's don't have some small numbers as factors and only consider those, or to first consider all k's and then remove them if they have the small factors? I'm pretty sure Prime95 and other modern implementations would have already asked this and have chosen the most efficient way.

Last fiddled with by Mini-Geek on 2010-11-03 at 17:34
Mini-Geek is offline