Wheel factorization: Efficient?

[science_man_88]

for(p=2,30,for(n=2,20,if((6*n*p+p)%24 == 7 || (6*n*p-p)%24 == 7,print(floor((6*n*p-p)/24)","p)))) I had 14 in there lol

(10:11) gp > forprime(p=1,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)))
2,5
7,5
12,5
17,5
22,5
6,7
13,7
20,7
27,7
34,7
2,11
13,11
24,11
35,11
46,11
9,13
22,13
35,13
48,13
61,13
16,17
33,17
50,17
67,17
84,17
8,19
27,19
46,19
65,19
84,19
16,23
39,23
62,23
85,23
108,23
13,29
42,29
71,29
100,29
129,29

23 knocks 85 out. so we can knock this off the list the hard part with this new code is determining where it starts it's all pn+c where c is unknown. Of course this is a slow form I'd use the equations if I knew them knock out all in the sequence of that form. which is my other problem I can't tell which ones would match up if i find a pattern in that maybe I can delete them faster.

[3.14159]

Originally Posted by CRGreathouse

Are you just playing around with science_man_88? This is obviously a bad method, as I have explained -- far too slow to be useful for any purpose, regardless of how good the sieve is. (Even with a magical sieve that goes directly from one prime to the next it is far too slow.)

*facepalm* I am not asking for a primality proof via sieving alone. No one's ever made any such propositions. Stop building strawmen. The point of the sieve is to reduce the amount of candidates, so time is saved and less tests have to be done.

[CRGreathouse]

Originally Posted by 3.14159

*facepalm* I am not asking for a primality proof via sieving alone. No one's ever made any such propositions. Stop building strawmen. The point of the sieve is to reduce the amount of candidates, so time is saved and less tests have to be done.

Not what I said; yours is the strawman. Using that many candidates makes the method infeasible, whether you remove members by sieving, (pseudo)primality tests, or oracle. I've already posted full details on this.

[3.14159]

Originally Posted by CRGreathouse

Not what I said; yours is the strawman. Using that many candidates makes the method infeasible, whether you remove members by sieving, (pseudo)primality tests, or oracle. I've already posted full details on this.

Oh. He wants to test every integer up to his desired limits. I see.

[CRGreathouse]

Originally Posted by 3.14159

Oh. He wants to test every integer up to his desired limits. I see.

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.

[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.

I never said I'd test them I said I'd find them.

[CRGreathouse]

Originally Posted by science_man_88

I never said I'd test them I said I'd find them.

Find what? (Really, I'm not a mind-reader... give me a break.) The primes in the range?

[science_man_88]

Originally Posted by CRGreathouse

Find what? (Really, I'm not a mind-reader... give me a break.) The primes in the range?

I've given enough information so that ability isn't needed. depends on the range you want to knock out them to, also this depends on if I get help or not.

[CRGreathouse]

Originally Posted by science_man_88

depends on the range you want to knock out them to, also this depends on if I get help or not.

I don't know what you meant, so I hope that you'll understand if I don't help since you refuse to explain.

[science_man_88]

Originally Posted by CRGreathouse

I don't know what you meant, so I hope that you'll understand if I don't help since you refuse to explain.

1) all (6x-/+1)*p are composite so any time they cross 24n+7 it should turn out to be composite.

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).

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.

[3.14159]

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.

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)?

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.

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.