Wheel factorization: Efficient?

[science_man_88]

Originally Posted by CRGreathouse
If he wanted to test every integer in the range, it would take time O(n) with an oracle. But even if he could skip over the composites costlessly, and test only the primes with an oracle for Mersenne-ness, it would still take time O(n/log n). This is entirely infeasible, since the competing algorithm is easily O(log^3 n) -- that is, exponentially better.
This would be made far easier when you take the following into account:
Every Mersenne number is of the form 6n + 1, and so is every number of the form 24n + 7. If he's looking for prime Mersenne numbers, he should just test the prime Mersenne numbers to see whether or not subtracting seven yields divisibility by 24 and get his results from there. It'll only take a few minutes.

Quote:
Originally Posted by science_man_88
1) all (6x-/+1)*p are composite so any time they cross 24n+7 it should turn out to be composite.
You mean, whenever they happen to have a GCD of the form (24n + 7)?

Quote:
Originally Posted by science_man_88
2) all possible n needed to find all odd Mersenne numbers (including all Mersenne primes above 7 for 24n+7) should be in the sequence I stated if I understand a method to figure out a(n+1) from a(n).
How are all n needed? You only need the Mersenne numbers themselves to test for whether or not subtracting seven yields divisibility by 24.

Quote:
Originally Posted by science_man_88
3) if we find out what c is in p*n+c that fits the pattern in the sequences above all we need is to figure out when p*n+c and the sequence given are equal if they are we can eliminate that value from our list given the numbers get large we might have to find sequences to follow to knock them out instead of the numbers themselves.
Well, this seems a bit too vague to me. You're going to have to define what c, p, and n are. Next, define the pattern and define the said sequences.

1) I mean when 6n*p+/-p = 24n+7
2) I'n not saying all n are needed I'm saying all n that give odd Mersenne numbers in either 6n+/-1 or 24n+7 are in the sequence given.
3) I don't have a defined value for c but p is a number (I prefer prime) n is a integer>=0 I think and that's about that.

[CRGreathouse]

Originally Posted by 3.14159

If he's looking for prime Mersenne numbers, he should just test the prime Mersenne numbers to see whether or not subtracting seven yields divisibility by 24 and get his results from there. It'll only take a few minutes.

That would be a quick test. I have a quick and equally effective test: do nothing. (2 to the power of any odd number > 1, minus 1, is 7 mod 24.)

[3.14159]

Originally Posted by science_man_88

1) I mean when 6n*p+/-p = 24n+7

Counterexample: 1567 is prime and it is 6n*p ± p and 24n + 7.

Next counterexample: 5023 is prime and it is 6n*p ± p and 24n + 7.

This one is false because 1567 and 5023 are primes and meet the requirements you made.

[3.14159]

Originally Posted by CRGreathouse

That would be a quick test. I have a quick and equally effective test: do nothing. (2 to the power of any odd number > 1, minus 1, is 7 mod 24.)

Hmm.. 2^5-1 = 31 = 7 mod 24
2^11-1 = 2047 = 7 mod 24.

That seems to be correct.

[CRGreathouse]

Originally Posted by 3.14159

Hmm.. 2^5-1 = 31 = 7 mod 24
2^11-1 = 2047 = 7 mod 24.

That seems to be correct.

8 * 4 = 8 (mod 24), so 2^(2n+1) = 2^(2n+3) (mod 24). Subtract 1 to get the required equality.

[3.14159]

Originally Posted by CRGreathouse

8 * 4 = 8 (mod 24), so 2^(2n+1) = 2^(2n+3) (mod 24). Subtract 1 to get the required equality.

The wonders of math.

2) I'n not saying all n are needed I'm saying all n that give odd Mersenne numbers in either 6n+/-1 or 24n+7 are in the sequence given.

As CRG's proven, every Mersenne number is 24n + 7. Your conjecture turned out to be trivially true. Also: For your first condition, the law of small numbers was at work there.

[science_man_88]

Originally Posted by 3.14159

Counterexample: 1567 is prime and it is 6n*p ± p and 24n + 7.

Next counterexample: 5023 is prime and it is 6n*p ± p and 24n + 7.

okay you're first counter example seems to me to only work for p=1 I state later p in p*n+c (which by the way should be the same p, is preferably prime) I'll admit i didn't say it had to be also any number that can be expressed as

6n*p+/-p = (6n+/-1)*p I'll admit if p is one it's prime so try it for primes.

anything I have given you that doesn't make sense ?

[3.14159]

Originally Posted by science_man_88

okay you're first counter example seems to me to only work for p=1 I state later p in p*n+c (which by the way should be the same p, is preferably prime) I'll admit i didn't say it had to be also any number that can be expressed as

Nono, P was not 1. The p that was used in the addition was 7. The other p was 13. I ensured N was divisible by 4.

[CRGreathouse]

Originally Posted by 3.14159

As CRG's proven, every Mersenne number is 24n + 7. Your conjecture turned out to be trivially true.

Not his conjecture, presumably, but Artur Jasinski's: A135659. Of course it was known long before that.

[CRGreathouse]

Originally Posted by science_man_88

okay you're first counter example seems to me to only work for p=1 I state later p in p*n+c (which by the way should be the same p, is preferably prime) I'll admit i didn't say it had to be also any number that can be expressed as

6n*p+/-p = (6n+/-1)*p I'll admit if p is one it's prime so try it for primes.

anything I have given you that doesn't make sense ?

You write p twice and n twice. Is this intentional? That is, do we need to find a pair (n, p) with

or a quadruple (m, n, p, q) with

or a triple (m, n, p) with

?

My best guess was the last, the literal wording suggests the first, and Pi seems to have guessed the second. OF course other interpretations may be possible.

p and q are primes and m,n natural numbers, presumably.

[science_man_88]

Originally Posted by 3.14159

Nono, P was not 1. The p that was used in the addition was 7. The other p was 13. I ensured N was divisible by 4.

oops I forgot about odd multiples of 7 I included that counter in my later codes (I think) thank's for my idiot title Pi.

I'm almost positive anything without these counters work and if we can figure the pattern to p*n+c that work for each p then we just have to find an equation to eliminate when they equal 4x+1 and relate 4x+1 values to n values to plug into a(n+1) = 4*a(n)+1 if I'm right to figure what indexes don't give primes. long road I know.

latest code I used was:

for(p=5,30,for(n=1,20,if((6*n*p+p)%24==7 || (6*n*p-p)%24==7,print(floor((6*n*p-p)/24)","p))))