Wheel factorization: Efficient?

[3.14159]

Originally Posted by CRGreathouse

Your guess is as good as mine. You can see where I assumed (explicitly!) that it was a prime (before #334), so I was confused as well.

Now that we're busy dealing with variable semantics, I forgot what the "conjecture" was.

[science_man_88]

Originally Posted by CRGreathouse

I don't remember which you've linked to. The 4^n plus-or-minus-something sequence? The 24n+7 seq? Mersenne primes? Mersenne exponents? Something else?



OK. So we're given a p > 1 and we have a function f. Let f(p) = c. Then you're looking at the values of px + c for all x in some unspecified range. Each one you find (or some of the ones you find) will sieve out composit values of 24m + 7 for m in some unspecified range. Correct?

if i interpret you correctly yes and hence if we can turn the patterns of f(p) towards 4(4n+1)+1 which this sequence seems to follow we can weed out the ones that can't be prime leaving the only ones that are prime and hence by counting the index into this sequence(better than using the numbers themselves) we can assuming a(0) gives you 2^3-1 show (2*index+3) is a exponent that will have to give a Mersenne prime.

[3.14159]

Originally Posted by science_man_88

p can be just prime as i just said. A002450

You couldn't use numbers from that sequence because some of them are divisible by three!

[science_man_88]

Originally Posted by 3.14159

You couldn't use numbers from that sequence because some of them are divisible by three!

I want to use the index as the numbers get to big fast. and then 2*index+3 = prime exponent for a Mersenne prime.

the sequence would be all possible m values for greater then 2^3-1 not the primes themselves.

[CRGreathouse]

Originally Posted by science_man_88

if i interpret you correctly yes and hence if we can turn the patterns of f(p) towards 4(4n+1)+1 which this sequence seems to follow we can weed out the ones that can't be prime leaving the only ones that are prime and hence by counting the index into this sequence(better than using the numbers themselves) we can assuming a(0) gives you 2^3-1 show (2*index+3) is a exponent that will have to give a Mersenne prime.

So you have an array of numbers: 7, 7 + 24, 7 + 24*2, .... You then remove multiples of p + c, multiples of 2p + c, multiples of 3p + c, ... up to Lp + c? Something like that? (This assumes that the thing from which you will "weed out the ones that can't be prime" is the sequence 24m + 7, and that the range for x starts at 1 and ends at L.)

You mention 4(4n+1)+1 = 16n + 5; what does it mean that you're turning the pattern of f(p) toward that?

Where does the sequence (4^n - 1)/3 come into play?

[science_man_88]

Originally Posted by CRGreathouse

So you have an array of numbers: 7, 7 + 24, 7 + 24*2, .... You then remove multiples of p + c, multiples of 2p + c, multiples of 3p + c, ... up to Lp + c? Something like that? (This assumes that the thing from which you will "weed out the ones that can't be prime" is the sequence 24m + 7, and that the range for x starts at 1 and ends at L.)

You mention 4(4n+1)+1 = 16n + 5; what does it mean that you're turning the pattern of f(p) toward that?

Where does the sequence (4^n - 1)/3 come into play?

(4^n-1)/3 seems to fit a(n+1)=4*a(n)+1

so 4(4n+1)+1 = 16n+5

turning towards that means telling when they are equal so for example 23 gave 85 with my pattern 85 is in this sequence it now is shown not to hold a Mersenne prime. I'd rather target the index in the sequence though.

you have a sequence p*x+c when this hits a number in the sequence it gets eliminated as a possible m for a 24m+7 Mersenne prime.

and 24(a(n))+7 is a odd Mersenne number.

[CRGreathouse]

So... this may be going out on a limb... but you're suggesting trial-dividing potential Mersenne numbers by numbers of the form (4^n-1)/3?

[science_man_88]

Originally Posted by CRGreathouse

So... this may be going out on a limb... but you're suggesting trial-dividing potential Mersenne numbers by numbers of the form (4^n-1)/3?

well using these sequence patterns to eliminate them but essentially yeah but maybe using a pattern in the indexes knocked out.

[CRGreathouse]

Originally Posted by science_man_88

well using these sequence patterns to eliminate them but essentially yeah but maybe using a pattern in the indexes knocked out.

OK, so you have a particular prime p for which 2^p - 1 may and may not be a Mersenne prime. You want to use the sequence (4^n-1)/3 in some fashion to eliminate p, that is, to prove that 2^p - 1 is composite.

All I'll need to know is
1. what range of n to use, and
2. how to determine, given (4^n-1)/3, if 2^p - 1 is composite (or unknown).

[3.14159]

Originally Posted by science_man_88

well using these sequence patterns to eliminate them but essentially yeah but maybe using a pattern in the indexes knocked out.

That's simply terrible!

Ex: 2^97 - 1 = 158456325028528675187087900671 = 11447 * 13842607235828485645766393.

None of those factors could be (4^n-1)/3 because they don't end in 1 or 5! This cannot be used.

[science_man_88]

Originally Posted by 3.14159

That's simply terrible!

Ex: 2^97 - 1 = 158456325028528675187087900671 = 11447 * 13842607235828485645766393.

None of those factors could be (4^n-1)/3 because they don't end in 1 or 5! This cannot be used.

look 24m+7 = odd 2^p-1 starting at 2^3-1. gives all odd exponent Mersenne numbers from 2^3-1 on.

so by determining if m is in the sequence by using the pattern of m derived to be composite using my method we can eliminate all odd composite 2^p-1 of form 24m+7 given a pattern in index elimination we could use this like a sieve of Eratosthenes on the indexes of the sequence given hence only leaving ones that can give primes any sieve of Atkins variant on this would be greatly loved.