mersenneforum.org Combined Sieving?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2005-07-14, 00:32 #1 jaat     Jul 2005 2·32 Posts Combined Sieving? Hi, I want to know whether I can do combined sieving for a bunch of k together with newpgen or some other tool? The issue is not to save time but save a lot of bother doing it for each k independently. jaat
 2005-07-16, 03:04 #2 geoff     Mar 2003 New Zealand 48516 Posts I don't know of any sieving program that will do this yet. But with pfgw you can use an ABC2 file to do trial factoring and prp testing for a number of k values. As an example, put this in myfile.txt: Code: ABC2 $a*5^$b-1 //{number_primes,$a,1} a: in { 1002 2004 } b: from 100 to 1000 and starting pfgw as 'pfgw -f myfile.txt' will trial factor and/or prp test 1002*5^100-1, 2004*5^100-1, 1002*5^101-1, ... etc. When one prp is found for a value of$a then testing will stop for that value and continue just for the remaining values. This is convenient, but will be much slower than sieving with newpgen unless the range for each k is quite small.
 2005-10-12, 10:34 #3 axn     Jun 2003 4,919 Posts Maybe its time we gave serious though to combined sieving. Can someone get in touch with Mikael Klasson to get a modified version of proth_sieve that can handle base 5? No idea how tough it'll be to do this, but i guess its worth a shot.
2005-10-26, 17:55   #4
jaat

Jul 2005

100102 Posts

Quote:
 Originally Posted by axn1 Maybe its time we gave serious though to combined sieving.

If there is any hope for this project to gather some momentum, this is a must.

jaat

 2005-11-30, 19:05 #5 Greenbank     Jul 2005 2·193 Posts Even if you can get this done it's going to be much slower. You lose all of the Quadratic Residue filtering. All of the small-steps will have to be calculated with powmod instead of simple bit shifts. The order(2) filtering will be gone (although you might be able to adapt this to base 5. Better off finding a program that implements base 5 sieving now as there would have been some attempts at optimising this sieving. proth_sieve only implements base 2, and therefore it is only optimised for base 2.
 2006-04-18, 02:26 #6 geoff     Mar 2003 New Zealand 13·89 Posts Riesel5 candidate k=151026 is the only one satisfying k = 0 (mod 3). This makes it the only remaining candidate that could have primes for both odd and even exponents. The possibilities for any other candidates are: If k = 1 (mod 3) then k*5^even-1 and k*5^odd+1 are composite If k = 2 (mod 3) then k*5^odd-1 and k*5^even+1 are composite [3 | k*5^n+/-1 whenever 3 | k*5^(n-2)+/-1 because 5^2 = 1 (mod 3)]. This fact could be exploited by a siever, for example to halve the memory required for a bitmap of candidate n (assuming k=151026 is not in the sieve). NewPGen does not seem to take advantage of this.

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post Christenson Hardware 12 2011-10-27 03:41 ltd Prime Sierpinski Project 76 2008-07-25 11:44 Joe O Prime Sierpinski Project 7 2006-09-22 09:34 Joe O Prime Sierpinski Project 35 2006-09-01 13:44 Citrix Prime Sierpinski Project 14 2005-12-31 19:39

All times are UTC. The time now is 14:09.

Tue Apr 20 14:09:36 UTC 2021 up 12 days, 8:50, 0 users, load averages: 3.35, 3.90, 3.75

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.