Wheel factorization: Efficient?

[CRGreathouse]

Originally Posted by science_man_88

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 ?

So you're suggesting that we can rule out numbers as Mersenne primes by trial division? Yes, that's a good method.

[science_man_88]

Originally Posted by CRGreathouse

So you're suggesting that we can rule out numbers as Mersenne primes by trial division? Yes, that's a good method.

sarcasm I'm guessing. this reminds me of something I raised about http://www.research.att.com/~njas/sequences/A002450

[3.14159]

Originally Posted by CRGreathouse

So you're suggesting that we can rule out numbers as Mersenne primes by trial division? Yes, that's a good method.

Hey, CRG! That gives me a good idea about posting in the kook Mersenne prediction thread! !

[CRGreathouse]

Originally Posted by science_man_88

sarcasm I'm guessing.

Not sarcasm, just pointing out that this method is well-known. It *is* a good method.

Originally Posted by science_man_88

this reminds me of something I raised about http://www.research.att.com/~njas/sequences/A002450

You refer, I assume, to your thread 6*(4x+1)+1.

I think the fundamental problem here is that you're trying to use properties of the arithmetic sequence 24n + 7 to determine things about 2^p - 1, but 24n + 7 is so fat (contains ~ x/8log(x) primes up to x) that it's hard to say much at all about a sequence as thin as 2^p - 1 (which contains << log(x)/log(log(x)) primes up to x, probably only log(log (x)) primes).

We're looking for needles in haystacks, but you're suggesting looking for needles in an exponentially bigger haystack... conjecturally, a double-exponentially bigger haystack.

[science_man_88]

Originally Posted by CRGreathouse

Not sarcasm, just pointing out that this method is well-known. It *is* a good method.



You refer, I assume, to your thread 6*(4x+1)+1.

I think the fundamental problem here is that you're trying to use properties of the arithmetic sequence 24n + 7 to determine things about 2^p - 1, but 24n + 7 is so fat (contains ~ x/8log(x) primes up to x) that it's hard to say much at all about a sequence as thin as 2^p - 1 (which contains << log(x)/log(log(x)) primes up to x, probably only log(log (x)) primes).

We're looking for needles in haystacks, but you're suggesting looking for needles in an exponentially bigger haystack... conjecturally, a double-exponentially bigger haystack.

okay but can we turn those n values in 24n+7 that give primes into 2^p-1 numbers is there a way to convert ?

[CRGreathouse]

Originally Posted by science_man_88

okay but can we turn those n values in 24n+7 that give primes into 2^p-1 numbers is there a way to convert ?

Sure. Just start at 7 and go upward 24 at a time, testing each member for primality. If you find a prime, add 1 and then see if the result is a power of 2. If so, output it; it's a Mersenne prime.

If you can prove primality in time O(log^4 n) then this takes time O(x log^4 x) to find the Mersenne primes up to x. If you pretest with Miller-Rabin, the time drop to O(x log^3 x).

If you use Lucas-Lehmer, it takes time O(log^3 x log log log x).

[science_man_88]

Originally Posted by CRGreathouse

Sure. Just start at 7 and go upward 24 at a time, testing each member for primality. If you find a prime, add 1 and then see if the result is a power of 2. If so, output it; it's a Mersenne prime.

If you can prove primality in time O(log^4 n) then this takes time O(x log^4 x) to find the Mersenne primes up to x. If you pretest with Miller-Rabin, the time drop to O(x log^3 x).

If you use Lucas-Lehmer, it takes time O(log^3 x log log log x).

I have a faster way using the 6(4x+1)+1 sequence I talked of earlier 24(1)+7 = 31

24(5)+7 = 127
24(21)+7 = 511

can we knock out a lot of the sequence through using comparison of 24n+7 intersecting the list made by (6n-/+1)*p ?

[CRGreathouse]

Originally Posted by science_man_88

can we knock out a lot of the sequence through using comparison of 24n+7 intersecting the list made by (6n-/+1)*p ?

I don't know what you mean by that. It seems like a suggestion for some form of trial division, which would not be faster than the (very slow) method I proposed above.

[science_man_88]

Originally Posted by CRGreathouse

I don't know what you mean by that. It seems like a suggestion for some form of trial division, which would not be faster than the (very slow) method I proposed above.

so starting with less and figuring a pattern to knock them out isn't going to be more efficient ?

[CRGreathouse]

Originally Posted by science_man_88

so starting with less and figuring a pattern to knock them out isn't going to be more efficient ?

Your pattern is so dense that even if you could knock out one per nanosecond it would still be too slow.

[science_man_88]

Originally Posted by CRGreathouse

Your pattern is so dense that even if you could knock out one per nanosecond it would still be too slow.

I'm talking knocking possible 1000's or more out with every pattern found.