View Single Post
Old 2010-11-04, 16:37   #9
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

56258 Posts
Default

You want to combine those factors (2kp+1) = +/- 1 (mod 8) with those that can be prime (2kp+1)= +/- 1 (mod 6).

Prime95 already does this, but instead of using +/- 1 mod 6, it uses those numbers mod 120 which can be prime, i.e. those that are co-prime with 120:
1,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59,61,67,71,73,77,79,83,89,91,97,101,103,107,109,113,119

Combining the above list with the requirement +/- 1 mod 8 gives 16 residue classes mod 120, which is those 16 Prime95 uses:
1,7,17,23,31,41,47,49,71,73,79,89,97,103,113,119

Your idea gives 20 residue classes mod 120:
1,7,17,23,25,31,41,47,49,55,65,71,73,79,89,95,97,103,113,119
so what Prime95 already uses is more efficient.
ATH is offline