Wheel factorization: Efficient?

[axn]

Originally Posted by 3.14159

Well, if you insist, I used 1/(ln(x)-1). That gave me about 1 in 92282. Eliminating multiples of 2 and 3 gives 1 in 30760. But it's actually closer to 1 in 30761.

How/why did you eliminate the multiple of 3?

[3.14159]

Originally Posted by axn

How/why did you eliminate the multiple of 3?

@Axn: Because I wished to increase the chances of success, and I've also already found a prime for that range: 207408 * 77906⁸¹⁹² + 1 (40078 digits)

[axn]

Originally Posted by 3.14159

@Axn: Because I wished to increase the chances of success, and I've also already found a prime for that range: 207408 * 77906⁸¹⁹² + 1 (40078 digits)

I meant, what was the mathematical basis for accounting for 3 in the calculation of odds?

[3.14159]

Originally Posted by axn

I meant, what was the mathematical basis for accounting for 3 in the calculation of odds?

Why not? Only odd integers are considered for testing, and the multiples of three are unnecessary, because they're easy to get rid of. Why should they not be accounted for?

[CRGreathouse]

Originally Posted by 3.14159

Why not? Only odd integers are considered for testing, and the multiples of three are unnecessary, because they're easy to get rid of. Why should they not be accounted for?

You can remove multiples of 2 because your numbers are all odd. You can't remove mutiples of 3 because some of your numbers are divisible by 3. (Sure, you can trial-divide as high as you like, but that on;y gives you the answers faster, it doesn't increase the number of primes.)

[3.14159]

Originally Posted by CRGreathouse

You can remove multiples of 2 because your numbers are all odd. You can't remove mutiples of 3 because some of your numbers are divisible by 3. (Sure, you can trial-divide as high as you like, but that on;y gives you the answers faster, it doesn't increase the number of primes.)

Why can't I remove multiples of three? Primes are either 6n + 1 or 6n - 1. It's completely acceptable to remove multiples of 2 and 3, including odd multiples of three.

Also: Numbers where (7ⁿ -1)/6 are prime: 5, 13, 131, 149, 1699, etc..

[CRGreathouse]

Originally Posted by 3.14159

Why can't I remove multiples of three? Primes are either 6n + 1 or 6n - 1. It's completely acceptable to remove multiples of 2 and 3, including odd multiples of three.

That has no bearing here. No numbers of the form k * 6^n + 1 are divisible by 2 or 3 so we can remove 2 and 3 when calculating the likelihood of a random number of that form being prime. No numbers of the form k * 77906^n + 1 are divisible by 2 or 38953, but some are divisible by 3 (e.g., 5*77906^8192+1).

Originally Posted by 3.14159

Numbers where (7ⁿ -1)/6 are prime: 5, 13, 131, 149, 1699, etc..

That's Sloane's A004063. It continues 14221, 35201, 126037, 371669, ....

[science_man_88]

(09:41) gp > forprime(p=5,100,for(n=1,p,if((p*n)%6==5,print1(n",");if(n==p-4 || n==p-2,print("_"p)))))
1,_5
5,_7
1,7,_11
5,11,_13
1,7,13,_17
5,11,17,_19
1,7,13,19,_23
1,7,13,19,25,_29
5,11,17,23,29,_31
5,11,17,23,29,35,_37
1,7,13,19,25,31,37,_41
5,11,17,23,29,35,41,_43
1,7,13,19,25,31,37,43,_47
1,7,13,19,25,31,37,43,49,_53
1,7,13,19,25,31,37,43,49,55,_59
5,11,17,23,29,35,41,47,53,59,_61
5,11,17,23,29,35,41,47,53,59,65,_67
1,7,13,19,25,31,37,43,49,55,61,67,_71
5,11,17,23,29,35,41,47,53,59,65,71,_73
5,11,17,23,29,35,41,47,53,59,65,71,77,_79
1,7,13,19,25,31,37,43,49,55,61,67,73,79,_83
1,7,13,19,25,31,37,43,49,55,61,67,73,79,85,_89
5,11,17,23,29,35,41,47,53,59,65,71,77,83,89,95,_97
(09:42) gp > forprime(p=5,100,for(n=1,p,if((p*n)%6==1,print1(n",");if(n==p,print("_"p)))))
5,_5
1,7,_7
5,11,_11
1,7,13,_13
5,11,17,_17
1,7,13,19,_19
5,11,17,23,_23
5,11,17,23,29,_29
1,7,13,19,25,31,_31
1,7,13,19,25,31,37,_37
5,11,17,23,29,35,41,_41
1,7,13,19,25,31,37,43,_43
5,11,17,23,29,35,41,47,_47
5,11,17,23,29,35,41,47,53,_53
5,11,17,23,29,35,41,47,53,59,_59
1,7,13,19,25,31,37,43,49,55,61,_61
1,7,13,19,25,31,37,43,49,55,61,67,_67
5,11,17,23,29,35,41,47,53,59,65,71,_71
1,7,13,19,25,31,37,43,49,55,61,67,73,_73
1,7,13,19,25,31,37,43,49,55,61,67,73,79,_79
5,11,17,23,29,35,41,47,53,59,65,71,77,83,_83
5,11,17,23,29,35,41,47,53,59,65,71,77,83,89,_89
1,7,13,19,25,31,37,43,49,55,61,67,73,79,85,91,97,_97

[science_man_88]

of course all this means is take (6*n+/-1)*p(a prime) as a subsequence that can't contain primes.

can we tell when 24n+7 wouldn't hit one of these ? if so maybe we can use that to help with speeding up the Mersenne prime search.

[CRGreathouse]

Originally Posted by science_man_88

can we tell when 24n+7 wouldn't hit one of these ? if so maybe we can use that to help with speeding up the Mersenne prime search.

What does this mean?

[science_man_88]

Originally Posted by CRGreathouse

What does this mean?

according to every person I know all mersenne primes>7 are 24n+7

since every (6n+/-1)*p number is a multiple of a number they can't be prime so if 24n+7 hits one it's not prime can we use this to predict which n for 24n+7 are prime and which ones are Mersenne primes ?