Wheel factorization: Efficient? - Page 27

3.14159 · 2010-08-02, 22:23

How about you simply program a sieve that eliminates numbers 24k + 7 that are obviously composite, to the desired prime that you wish to eliminate? That would make an excellent idea.

Ex: Code for the elimination of divisors 7, 11, 13, 17, 19, 23, 29, 31, 37, ... up to 10^6 (Set a high primelimit if you're going to try it in PARI.)
That'll get rid of 90% of the candidates, and test the 10% for primality.

After you finish writing a program for a sieve, turn it into an executable, and test it out. Then, post your data here. Or, even easier, try coding this in PARI and post your results.

CRGreathouse · 2010-08-02, 22:40

Quote:

Originally Posted by science_man_88

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

You could remove a trillion each time and it would be too slow.

Consider: Below a googol there are about 5.45e96 primes of the form 24n + 7. If you remove a trillion per nanosecond, it'll take 5.45e75 seconds > 10^68 years. If you use Lucas-Lehmer, you need to do $\pi(\lg(10^{100}))=67$ tests, which will take less than a second overall. (Of course the number of tests can be reduced by trial division and other methods, but this only makes LL look better.)

3.14159 · 2010-08-02, 22:42

Is he trying to prove primality via sieving or trial division alone? If not, CRG, your point's invalidated.

@Scienceman: Post data whenever you have the chance.

P.S: I was able to do an amateur implementation myself:
Out of 10000 candidates: 976 were retrieved after going up to 17. 526 were prime; 450 were composite. Rarity: More primes than composites?
A snippet of data:

Code:

271 is prime
367 is prime
439 is prime
463 is prime
487 is prime
607 is prime
631 is prime
703 is composite
727 is prime
751 is prime
823 is prime
919 is prime
943 is composite
967 is prime
991 is prime
1039 is prime
1063 is prime
1087 is prime
1159 is composite
1231 is prime
1279 is prime
1303 is prime
1327 is prime
1399 is prime
1423 is prime
1447 is prime
1471 is prime
1543 is prime
1567 is prime
1591 is composite
1663 is prime
1711 is composite
1759 is prime
1783 is prime
1831 is prime
1879 is prime
1927 is composite
1951 is prime
1999 is prime
2047 is composite
2071 is composite
2143 is prime
2239 is prime
2263 is composite
2287 is prime
2311 is prime
2383 is prime
2407 is composite
2479 is composite
2503 is prime
2551 is prime
2599 is composite
2623 is composite
2647 is prime
2671 is prime
2719 is prime
2767 is prime
2791 is prime
2887 is prime
2911 is composite
2983 is composite
3007 is composite
3079 is prime
3103 is composite
3127 is composite
3151 is composite
3271 is prime
3319 is prime
3343 is prime
3391 is prime
3439 is composite
3463 is prime
3511 is prime
3559 is prime
3583 is prime
3607 is prime
3631 is prime
3727 is prime
3799 is composite
3823 is prime
3847 is prime
3919 is prime
3943 is prime
3967 is prime
4087 is composite
4111 is prime
4159 is prime
4183 is composite
4231 is prime
4327 is prime
4351 is composite
4399 is composite
4423 is prime
4447 is prime
4519 is prime
4567 is prime
4591 is prime
4639 is prime
4663 is prime
4687 is composite
4759 is prime
4783 is prime
4831 is prime
4903 is prime
4951 is prime
4999 is prime
5023 is prime
5119 is prime
5143 is composite
5167 is prime
5191 is composite
5263 is composite
5311 is composite
5359 is composite
5407 is prime
5431 is prime
5479 is prime
5503 is prime
5527 is prime
5623 is prime
5647 is prime
5671 is composite
5743 is prime
5767 is composite
5791 is prime
5839 is prime
5911 is composite
5959 is composite
5983 is composite
6007 is prime
6031 is composite
6079 is prime
6151 is prime
6199 is prime
6247 is prime
6271 is prime
6319 is composite
6343 is prime
6367 is prime
6439 is composite
6463 is composite
6583 is composite
6607 is prime
6631 is composite
6679 is prime
6703 is prime
6751 is composite
6823 is prime
6847 is composite
6871 is prime
6943 is composite
6967 is prime
6991 is prime
7039 is prime
7087 is composite
7159 is prime
7207 is prime
7279 is composite
7303 is composite
7351 is prime
7471 is composite
7519 is composite
7543 is composite
7591 is prime
7639 is prime
7663 is composite
7687 is prime
7759 is prime
7783 is composite
7807 is composite
7831 is composite
7879 is prime
7927 is prime
7951 is prime
7999 is composite
8023 is composite
8119 is composite
8167 is prime
8191 is prime
8263 is prime
8287 is prime
8311 is prime
8383 is composite
8431 is prime
8479 is composite
8527 is prime
8599 is prime
8623 is prime
8647 is prime
8719 is prime
8791 is composite
8839 is prime
8863 is prime
8887 is prime
9007 is prime
9103 is prime
9127 is prime
9151 is prime
9199 is prime
9223 is composite
9271 is composite
9319 is prime
9343 is prime
9391 is prime
9439 is prime
9463 is prime
9487 is composite
9511 is prime
9631 is prime
9679 is prime
9703 is composite
9727 is composite
9799 is composite
9847 is composite
9871 is prime
9943 is composite
9967 is prime
9991 is composite
10039 is prime
10063 is composite
10111 is prime
10159 is prime
10207 is composite
10279 is composite
10303 is prime
10327 is composite
10399 is prime
10447 is composite
10471 is composite
10519 is composite
10567 is prime
10639 is prime
10663 is prime
10687 is prime
10711 is prime
10783 is composite
10807 is composite
10831 is prime
10903 is prime
10951 is composite
11023 is composite
11047 is prime
11071 is prime
11119 is prime
11191 is composite
11239 is prime
11287 is prime
11311 is prime
11359 is composite
11383 is prime
11503 is prime
11527 is prime
11551 is prime
11623 is composite
11647 is composite
11719 is prime
11743 is prime
11839 is prime
11863 is prime
11887 is prime
11911 is composite
11959 is prime
11983 is composite
12007 is prime
12031 is composite
12079 is composite
12127 is composite
12151 is composite
12247 is composite
12319 is composite
12343 is prime
12367 is composite
12391 is prime
12487 is prime
12511 is prime
12559 is composite
12583 is prime
12679 is composite
12703 is prime
12751 is composite
12799 is prime
12823 is prime
12847 is composite
12871 is composite
12919 is prime
12967 is prime
13063 is prime
13087 is composite
13159 is prime
13183 is prime
13207 is composite
13231 is composite
13303 is composite
13327 is prime
13399 is prime
13423 is composite
13471 is composite
13543 is composite
13567 is prime
13591 is prime
13639 is composite
13687 is prime
13711 is prime
13759 is prime
13807 is prime
13831 is prime
13879 is prime
13903 is prime
13927 is composite
13999 is prime
14023 is composite
14071 is prime
14143 is prime
14167 is composite
14191 is composite
14239 is composite
14359 is composite
14383 is composite
14407 is prime
14431 is prime
14479 is prime
14503 is prime

science_man_88 · 2010-08-02, 22:48

Quote:

Originally Posted by 3.14159

Is he trying to prove primality via sieving or trial division alone? If not, CRG, your point's invalidated.

I know that the sequence I gave is all the possible n for all odd Mersenne numbers

Code:

(19:37) gp > forprime(p=1,30,for(n=1,20,if((6*n*p+p)%14 == 7 || (6*n*p-p)%14 == 7,print(n","p))))
1,3
6,3
8,3
13,3
15,3
20,3
1,5
6,5
8,5
13,5
15,5
20,5
1,7
2,7
3,7
4,7
5,7
6,7
7,7
8,7
9,7
10,7
11,7
12,7
13,7
14,7
15,7
16,7
17,7
18,7
19,7
20,7
1,11
6,11
8,11
13,11
15,11
20,11
1,13
6,13
8,13
13,13
15,13
20,13
1,17
6,17
8,17
13,17
15,17
20,17
1,19
6,19
8,19
13,19
15,19
20,19
1,23
6,23
8,23
13,23
15,23
20,23
1,29
6,29
8,29
13,29
15,29
20,29

this shows most p that I've checked seem to fit both 7x+1/+6

now this is for the 6np+/-p for n I should figure out what it is for 24n+7 then all members of the sequence that fit this can be eliminated.

science_man_88 · 2010-08-02, 23:00

Code:

(19:51) gp > forprime(p=1,30,for(n=1,20,if((6*n*p+p)%14 == 7 || (6*n*p-p)%14 == 7,print(floor((6*n*p-p)/14)","p))))
1,3
7,3
10,3
16,3
19,3
25,3
1,5
12,5
16,5
27,5
31,5
42,5
2,7
5,7
8,7
11,7
14,7
17,7
20,7
23,7
26,7
29,7
32,7
35,7
38,7
41,7
44,7
47,7
50,7
53,7
56,7
59,7
3,11
27,11
36,11
60,11
69,11
93,11
4,13
32,13
43,13
71,13
82,13
110,13
6,17
42,17
57,17
93,17
108,17
144,17
6,19
47,19
63,19
104,19
120,19
161,19
8,23
57,23
77,23
126,23
146,23
195,23
10,29
72,29
97,29
159,29
184,29
246,29

these all seem to have patterns to me but you can double check also can we relate this to p?

CRGreathouse · 2010-08-02, 23:39

Quote:

Originally Posted by 3.14159

Is he trying to prove primality via sieving or trial division alone? If not, CRG, your point's invalidated.

I was assuming he was proving primality with an oracle that lets him know, in one nanosecond, the primality of a trillion numbers of the form 24n + 7. If he doesn't have that kind of genie-in-a-bottle and has to use standard tests or trial division it will of course take much longer.

3.14159 · 2010-08-02, 23:59

Quote:

Originally Posted by CRGreathouse

I was assuming he was proving primality with an oracle that lets him know, in one nanosecond, the primality of a trillion numbers of the form 24n + 7. If he doesn't have that kind of genie-in-a-bottle and has to use standard tests or trial division it will of course take much longer.

Of course it would. Which is why I suggested that he build a sieve. By the way: I was able to make a sieve in PARI that eliminates the composite choices that are divisible by the primes up to 2297. Also: To jump on this idea further: Are there any arithmetic progression sieve implementations, whether it be executable or source code?

Also: Wiki is wrong on the record for arithmetic progression:
The largest known prime in an arithmetic progression = 2^43112609 - 1 (12978189 digits)

science_man_88 · 2010-08-03, 00:12

Quote:

Originally Posted by 3.14159

Of course it would. Which is why I suggested that he build a sieve. By the way: I was able to make a sieve in PARI that eliminates the composite choices that are divisible by the primes up to 2297. Also: To jump on this idea further: Are there any arithmetic progression sieve implementations, whether it be executable or source code?

Also: Wiki is wrong on the record for arithmetic progression:
The largest known prime in an arithmetic progression = 2^43112609 - 1 (12978189 digits)

yeah I know you all think I'm stupid the feeling seems mutual on this forum. I have found a pattern within the patterns I found before for this there is a few things i need to figure out willing to offer a hand ?

CRGreathouse · 2010-08-03, 00:21

Quote:

Originally Posted by 3.14159

By the way: I was able to make a sieve in PARI that eliminates the composite choices that are divisible by the primes up to 2297.

Why so small? I'd want to sieve to at least 1e8. Or,rather, when I built a quick siever for a similar problem, I sieved to ~1e9.

Quote:

Originally Posted by 3.14159

Also: Wiki is wrong on the record for arithmetic progression:
The largest known prime in an arithmetic progression = 2^43112609 - 1 (12978189 digits)

I assume you refer to the table here:
http://en.wikipedia.org/wiki/Primes_...ic_progression

It lists the largest k-APs of primes for k = 3..26. You give a single number rather than a tuple; what are the other 2 to 25 numbers you were thinking of?

CRGreathouse · 2010-08-03, 00:27

Quote:

Originally Posted by science_man_88

I have found a pattern within the patterns I found before for this there is a few things i need to figure out willing to offer a hand ?

I'm willing to help, but you know that you'll need to spell things out for me -- I can't pick up on your implications too well.

3.14159 · 2010-08-03, 00:35

Quote:

Originally Posted by CRGreathouse

Why so small? I'd want to sieve to at least 1e8. Or,rather, when I built a quick siever for a similar problem, I sieved to ~1e9.

Because I don't know how to build efficient code for it. Or did you type "if x%2!=0 and x%3!=0 ... and x%156577 !=0 ... and x%597811057 !=0..."

Damned NewPGen doesn't allow 1 for an exponent.

2010-08-02, 22:23	#287
3.14159 May 2010 Prime hunting commission. 11010010000₂ Posts	How about you simply program a sieve that eliminates numbers 24k + 7 that are obviously composite, to the desired prime that you wish to eliminate? That would make an excellent idea. Ex: Code for the elimination of divisors 7, 11, 13, 17, 19, 23, 29, 31, 37, ... up to 10^6 (Set a high primelimit if you're going to try it in PARI.) That'll get rid of 90% of the candidates, and test the 10% for primality. After you finish writing a program for a sieve, turn it into an executable, and test it out. Then, post your data here. Or, even easier, try coding this in PARI and post your results. Last fiddled with by 3.14159 on 2010-08-02 at 22:39

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Wheel Factorization	a1call	Factoring	11	2017-06-19 14:04
Efficient Test	paulunderwood	Computer Science & Computational Number Theory	5	2017-06-09 14:02
LL tests more credit-efficient than P-1?	ixfd64	Software	3	2011-02-20 16:24
A Wheel	storm5510	Puzzles	7	2010-06-25 10:29
Most efficient way to LL	hj47	Software	11	2009-01-29 00:45