20200106, 13:36  #1 
Oct 2019
17 Posts 
Question about sieving
Hi, I'm currently using newpgen to sieve a range for proth primes but I suspect the software that primegrid uses (sr2ppsieve, in my case I would use the CUDA version) would be much faster than that. Am I right? If yes, were can I download that program?

20200106, 14:02  #2 
"Mark"
Apr 2003
Between here and the
3·2,143 Posts 
What range are you sieving? Are you sieving fixed k or fixed n? Just want to see if you are using the optimal software for sieving as newpgen is much slower than many other sieveing programs, depending upon what you are sieving.

20200106, 14:18  #3 
Oct 2019
17_{10} Posts 
Hi! I was thinking to get into prime testing outside big projects (GIMPS and PrimeGrid), so I was just experimenting a little bit with random values.
I thought that the only possible sieving was with fixed n so I was doing n=4156789 and Ks between 75000 and 95000 (as I stated, completely random). What ranges should I sieve with which program? I'm completely new to this and had no idea that the optimal program to use for sieving depended on the range. 
20200106, 21:20  #4  
"Mark"
Apr 2003
Between here and the
3·2,143 Posts 
Quote:
The simplest ones that quickly come to mind are the Generalied Cullen and Generalized Woodall searches. I call these "simplest" because the form of the prime is easy to identify and have no special symbols. The search spaces are also fairly small compared to other projects so one quickly gets into the Top 5000 prime territory. Next up would be Carol/Kynea or Multifactorial. These forms are a little harder to understand as they have symbols beyond the +, , ^, and * operators. From there you find projects with more participants which means you are more at risk for poaching or searching ranges that have already been searched. This would include the Proth Prime Search, the Riesel Prime Search, and CRUS. The Riesel and Sierpinski forms have a lot of searchers and multiple projects, depending upon their focus. The search space is much larger than most other projects. For most of the smaller projects you are likely to use a program built upon the mtsieve framework. For full disclosure I wrote mtsieve and have assisted more prime searching projects here or at PrimeGrid than most others. I have not participated on GIMPS and my participation of PrimeGrid projects occurred before PrimeGrid grew to its current size. Once you have spent some time on smaller projects and have hopefully made some contributions, you should have more confidence to contribute to the larger projects without anyone denigrating any of your work. Last fiddled with by rogue on 20200106 at 21:20 

20200830, 16:21  #5 
Aug 2020
79*6581e4;3*2539e3
3×7×19 Posts 
Just for fun I wanted to do some manual hunting. To keep the CPUs on Primegrid, I want to do it with GPU only. I appears Proth primes are good candidates since there is both sieving and prime testing software for GPU available.
I want to have a fixed k (in 10^6 range far from PG's range) and sieve for n values around 10^6. Is sr2sieve the best choice? For primality testing the sieved candidates I want to use proth20, anyone used that before? Last fiddled with by bur on 20200830 at 16:40 
20200831, 00:23  #6  
"Mark"
Apr 2003
Between here and the
3·2,143 Posts 
Quote:


20200831, 06:59  #7  
Aug 2020
79*6581e4;3*2539e3
399_{10} Posts 
Quote:
Do you have any recommendation regarding newpgen vs sr2sieve? Or should I just try both? Also most Proth searches seem to focus on small k. Not just k < 2^n, but k <<< 2^n. Is there a reason for it, like higher efficiency per number of digits? And is there anything "special" about k values that are prime? I know there was some activity to find a prime k Cullen/Woodall, but not about Proth primes with k being prime. 

20200901, 08:44  #8  
"Jeppe"
Jan 2016
Denmark
2^{3}·3·7 Posts 
Quote:
But PrimeGrid is already doing all the low k in its different PPS (Proth Prime Search) flavors (PPSDIV, PPS, PPSE, PPSMEGA) and for k=3 in their "321" subproject. So to not conflict with PrimeGrid, in my opinion, you must pick a k over 10'000. For Proth candidates, there is nothing special about k that are prime (other than, again, aesthetics; many people's favorite numbers are primes). There is something special about k that are perfect cubes, fourth powers and so on; they admit algebraic factorizations of some candidates. So if your k happens to be of this type, be sure that the sieving software, or other software, removes candidates that have special factorizations. /JeppeSN 

20200901, 13:40  #9 
Aug 2020
79*6581e4;3*2539e3
3×7×19 Posts 
Thanks, I was planning k ~ 10^6 and maybe also k that are prime.
I have some questions about sieving: I tried sr2sieve and realized I don't really understand the output. It created a factors.txt which showed the factors and the number they divide found during sieving. But don't I need the opposite, a file that lists all potential candidates? And this file I'll feed to the primality test software? How do I tell sr2sieve to create that file? Also the readme said sr2sieve only handles factors larger than k, for smaller factors one should use newpgen oder srsieve. I think this isn't optional but highly recommended? Otherwise all numbers divisible by 3 or 5 or other small factors will remain as candidates. So I would use srsieve to sieve for factors <= k and then sr2sieve for factors > k? 
20200901, 15:20  #10  
"Curtis"
Feb 2005
Riverside, CA
4995_{10} Posts 
Quote:
One uses srfile to manipulate the files. srsieve outputs an srsieve.out file. The command "srfile a srsieve.out" converts this file to the abcd format that sr2sieve uses. sr2sieve creates factor files only because it is designed to be used across multiple machines in that use case, one wants to collect all the factor files from the various instances and apply them all to a single input file to remove all the factors. So, again srfile is used to do so: srfile k factors.txt sr_{base}.abcd a Or, if you're ready for LLR, you'd use G at the end rather than a to write a file in format LLR prefers. srfile h will show you all the available formats. 

20200901, 17:19  #11 
"Mark"
Apr 2003
Between here and the
1100100011101_{2} Posts 
If using sr2sieve with a k in that range, make sure that you generate the Legendre tables. That should give it a nice speed boost.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Sieving Question  __HRB__  Math  1  20190428 05:47 
Dumb sieving question  fivemack  Software  7  20171127 22:48 
Line sieving vs. lattice sieving  JHansen  NFSNET Discussion  9  20100609 19:25 
A question on lattice sieving  joral  Factoring  5  20080403 08:01 
Sieving question  jasong  Sierpinski/Riesel Base 5  9  20070723 00:03 