All Things SoB Sieving

 

The Seventeen or bust project is a distributed project that aims to prove the Sierpinski conjecture.  In order to achieve this, prime numbers need to be found for the (what was) 17 remaining numbers of the form k*2^n+1 for k less than 78557.  To date nine prime numbers have been found, leaving eight to find.

 

SoB Sieving is a sub-project that attempts to remove potential candidates by (intelligent) trial division.

 

Big positives:

Sieving can be run on any PC, even one that is not able to connect to the Internet. 

Sieving is a very efficient method of removing candidates.

Big negatives:

You will never find a prime by sieving, so unless you are participating in the main SoB project as well, you will never have the chance to have your name recorded in history! 

The sieving software has not been fully optimised for the P4, as a result like for like clock speeds, non-P4s will be about 3x faster.  P4 owners should consider the P-1 sub-project; take a look at this excellent site provided by hc_grove for more information, or the P-1 forum.

 

To sieve all you need is a computer, a client, a sob.dat file, and a range.

 

 

Regular sieving

 

Regular sieving covers the candidates that have not been doubled checked by the main part of the project (currently 1.40M < n < 20M).  A daily updated sob.dat should be used.  It is not important to update your sob.dat file every day, but if you do so every (say) month you should notice a small but gradual performance improvement.  A clear text version of the sob.dat file is available for information.  Also a very small zip file that has clear text .dat files that indicate the next couple of days of main and double check PRP efforts, and a log file that indicates the daily progress of the shrinkage of the sob.dat file, again just for info.  For safety (should anything go wrong with the daily updates) a static 1M < n < 20M sob.dat is available.

 

The recommended client to use for regular sieving is Proth Sieve.

 

Sieve ranges should be reserved here, results should be submitted here when ranges are completed.  Please ensure you are logged in when submitting factors

 

 

The Sieving clients

 

For Windows and Linux platforms, the client of choice is Proth Sieve provided by Mikael Klasson, with assistance from Paul Jobling.  Proth Sieve provides a command line interface, which allows the client to be incorporated in an automated, batch or service type environment.  Only PCs with very old processors should use the “regular” version.  PII, PIII and AMD users should opt for the cmov version, while P4 users should use the SSE2 version.  Mikael also provides a tool call sobistrator that allows multiple sieve clients to be managed from a single PC.

 

For those users that demand a windows GUI, the only option is SobSieve.exe provided by Paul Jobling.  SobSieve 1.34 provides an easy to use windows interface, although it should be noted that this client is about 40% slower the Proth Sieve.

 

For operating systems other than Windows and Linux, NbeGone is the client of choice, provided by Phil Charmody.  Check out the various operating systems supported here.  The SoB sieving part of Phil’s site is duplicated here for those innocent people who live in a country that is in some way supportive of the 2003/4 US/UK led invasion of Iraq.  If you do want to try accessing Phil’s site try searching for “public proxies country” in Google.

 

Sieve ranges should be reserved here, results should be submitted here when ranges are completed.  Submit very large factors here.  Please ensure you are logged in when submitting factors (otherwise scoring is not guaranteed).  As a rough guide, a 100G range will take 3 days on an AMD XP2100+, 6 days on a P3-850 and 15 days on a P2-400.  Again, as a rough guide, if that 100G range is around p=700T, expect it to yield about 3 factors.

 

The Seventeen or Bust forum is the place to find sieving discussions or more general Seventeen or Bust discussions. 

 

 

Scoring

 

All time and 2005 scores are provided for both sieving and P-1 factoring.  These are updated four times per day at about 03:00, 09:00, 15:00 and 21:00 UK local time.  Scoring is calculated as follows.

 

A unique factor scores as follows:
p < 40T, score = p/1T

p > 40T, in ‘main active' window, 0 PRP tests performed, score = (n/1M ^ 2) * 125 * bias

p > 40T, between ‘DC active window’ and ‘n upper bound’, 0 PRP tests performed, score = (n/1M ^ 2) * 125 * bias (then score will not increase further).
p > 40T, in 'DC active' window, 0 PRP tests performed, score = (n/1M ^ 2) * 125 * bias
p > 40T, in 'DC active' window, 1 PRP tests performed, score = (n/1M ^ 2) * 125 * 0.6 * bias
p > 40T, in 'DC active' window, 2 PRP tests performed, score = (n/1M ^ 2) * 125 * 0.2 * bias
p > 40T, in ‘completed' window, score = (n/1M ^ 2) * 125 * 0.2

p > 40T, k=prime; as above then frozen when a prime is found, factors found after the prime score 0
none of the above, score = (as duplicate, see below)

bias = p/40T or current 90% sieve point/40T, whichever is lower.


A duplicate factor will score as follows:
score = p/100T, capped at 35, or the score (above) as if it were unique, whichever is lower; when a prime is found all duplicates ever found for that k score 0.

A unique factor is the first factor found for a candidate.
Scores for each unique factor are remembered. Scores can go up (as an 'active' window moves to cover a factor that was above the window), but cannot go down (as a factor moves out of a window).

Scores with 0 PRP tests exiting the main active window will receive no further increase (i.e. no increase when they reach the DC active window).
The 'main active' windows is (<next candidate>) < n < (<next candidate> + 200K).

The ‘DC active' windows is (<next double check candidate>) < n < (<next double check candidate> + 200K)

A second ‘DC active' windows is (<next double check candidate2>) < n < (<next double check candidate2> + 10K)

The 'completed' windows is 0 < n < (<next double check candidate>)

‘n upper bound’ is the lowest of the ‘n bound (upper)’ described here

Excluded factors (those factors not present after sieving 100<n<20M to p=1G) do not score.

 

Before 21-July-2003 scores were calculated as follows:

 

n < 300K, score = p/1T * ((n*n)/(300K * 300K))
300K < n < 20, score = p/1T
n > 20M, score = p/1T *0.05
Duplicates, score = score * 0.01;
when a prime is found all duplicates ever found for that k score 0.

 

The lowest p for a k/n factor scored as the unique factor, all higher p scored as duplicates.

Excluded factors (those factors not present after sieving 100<n<20M to p=1G) do not score.

 

Additional information that is generated as a result of the scoring is a results.txt format file with duplicate and excluded factors marked, and user and team allocations fully identified.  This is updated daily at about 03:00.

 

 

Gap analysis

 

Here we attempt to determine those ranges have been fully sieved, and those that require further work.

 

0T<p<400T

400T<p<500T

500T<p<600T

600T<p<700T

700T<p<800T

800T<p<900T

900T<p<1000T

1000T<p<2000T

2000T<p<9990T

 

Summary 100T<p<1000T

 

All these are updated four times per day at about 03:00, 09:00, 15:00 and 21:00 UK local time.

 

 

Scoring History

 

Date

Event

User scores

Team scores

Project statistics

19 Oct 2005

Status soon after k= 4847 removed (first day of sieving 8 k).

user

team

project

19 Oct 2005

Status prior to prime found for k= 4847  (last day of sieving 9 k).

user

team

project

17 Jun 2005

Status soon after k= 27653 removed (first day of sieving 9 k).

user

team

project

16 Jun 2005

Status prior to prime found for k= 27653  (last day of sieving 10 k).

user

team

project

04 Jan 2005

Status soon after k= 28433 removed (first day of sieving 10 k).

user

team

project

03 Jan 2005

Status prior to prime found for k= 28433 (last day of sieving 11 k).

user

team

project

03 Sep 2004

300T completed

user

team

project

20 Dec 2003

Status soon after k=5359 removed (first day of sieving 11 k).

user

team

project

16 Dec 2003

Status prior to prime found for k=5359 (last day of sieving 12 k).

user

team

project

12 May 2003

Another early sieve statistic (17T completed).

combined

01 Apr 2003

Earliest sieve statistics I can find (10T completed).

combined

 

 

Other Useful Links

 

P-1 sub-project information provided by hc_grove.

A daily updated P-1 sob.dat – ONLY FOR P-1 factoring.  Use and regularly update with this file (only 16KB) and you don’t need to worry about downloading results.txt (1.9MB).

Background information on sieving ...and a bit more

SI units 10^-24 though 10^24

Largest known factors found using Pollard’s P-1 method (good indication of the B1 and B2 parameters that need to be used to break records, nothing from SoB yet!)

Largest 200 known primes (look for SBn in the who column for SoB contributions)

 

 

 

 

Any problems?  Contact me through the SoB forum here

 

Page last updated by Mike Henley, Saturday, 07 October 2006.