View Single Post
Old 2010-11-03, 17:39   #8
CRGreathouse's Avatar
Aug 2006

22·1,493 Posts

Originally Posted by Mini-Geek View Post
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.
In other words: the idea works and is probably already in use, unless a yet better way has been found by the Prime95 crew.
CRGreathouse is offline