Proth Primes: Search and Double-Check Status
log in

Introduction

Table below summarizes status of Proth Primes Search for K = 3…9999, N = 0…10M ranges. Historically, search for Proth primes was performed in different projects, lead by different peoples. Main goal of this work is to get a complete picture which ranges were tested and be sure (with a very high probability) that no primes were missed.

Any project can be affected by a human mistake (for example, a range erroneously skipped during manual loading of work) or database crash. Some projects had no error checking at all, they tried to find as much primes as possible not caring about possible calculations errors and missed primes. To be sure that no primes were missed, all historical records from all projects were reprocessed. A test is considered valid if it either has at least two matching results from two different users, either its correctness was confirmed by LLR2 certificate. Otherwise, the result is suspicious and must be double-checked.

There are two types of searches which must be double-checked:

PrpNet testing - PrpNet software is widely used for small searches - the server is much easier to setup, comparing to full-scale Boinc server. Proth PrpNet projects were running in "one-pass" mode - requiring only one result per candidate. It makes search faster, but has a big disadvantage that malfunctioning / overheating computer could generate any number of invalid results which will never be noticed. In real data of historical PrimeGrid PrpNet searches, about 1-2% of tests were invalid.

Adaptive replication (AR) work - AR is a special mode of Boinc server, where each computer is either "trusted" or "untrusted". When new computer successfully completes few tasks (validated by other users), it becomes "trusted". Results from trusted computer are accepted without additional verification. This scheme is better than simple "one-pass" mode (really bad computer will never get trusted status), but the problem is that computers may start glitching anytime - e.g. CPU may start to overheat due to dust or rising ambient / room temperature. Although server periodically double-checks work from trusted host to be sure that it's still valid, such host may return many invalid results before server notices a problem. In real data, about 0.1% of tests are invalid - as you can see, this number is very small, but invalid tests still do exist.

To help clean up suspicious ranges, join "LLR testing" project on this server. We're testing small N (currently N = 2M…3M and will go down), so tasks are short. High N will be tested on PrimeGrid as a part of current and future PrimeGrid subprojects.

The Gwnum problem

And now sad part of the story. Unfortunately, "two matching results" rule do not guarantees that result is valid. The core of all popular prime testing software (PFGW, LLR, Prime95) is a same library - "gwnum". This is a software masterpiece, but it's very, very complex thing which is known to have bugs and sometimes may produce invalid result. It's too complicated to describe in few words, but it's possible that two similar computers will return same invalid result, and problem will be unnoticed. It happens very rare, only near specific crossover points, but we already have few known examples of the problem. So why I said above about "high" - but not a strong 100% probability that no primes were missed. Gwnum bugs were fixed as we discovered them, but there are years of work made with old and buggy versions of LLR. Re-doing everything from scratch to find just a few potentially invalid results is way too much. May be our grandchildren will eventually do it as part of their homework :)

This is not a problem in Pavel Atnashev' LLR2, where two independent protection levels were added to verify correctness of result. Any calculation error will be noticed immediately. Big LLR projects on PrimeGrid (all except SGS and PPSE) and all LLR projects on this server are using LLR2 since 2020.

The Table

K500K1M1.422M1.65M2M2.41M3M3.05M3.322M3.64M4M6M9M10M
3To be determined
5 … 7OKNEED DC (AR)DC in progressOKUntested
9OKNEED DC (AR)DC in progressOKEven: Untested / Odd: OKUntested
11 … 25OKNEED DC (AR)DC in progressOKUntested
27OKEven: NEED DC (PrpNet) / Odd: OKNEED DC (PrpNet)
29 … 49OKNEED DC (AR)DC in progressOKUntested
51 … 99OKNEED DC (AR)DC in progressOKUntested
101 … 119OKNEED DC (AR)OKPG PPS projectOKUntested
121OKPG PPS projectOKNEED DC (PrpNet)
123 … 299OKNEED DC (AR)OKPG PPS projectOKUntested
301 … 1199OKNEED DC (AR)OKPG PPS projectOKUntested
1201 … 9999NEED DC (AR)OKPG PPSE projectPG PPS-MEGA project
K's which were tested separately in PG DIV project
1323NEED DC (AR)OKEven: OK / Odd: PG PPSE projectPG PPS-MEGA project
2187NEED DC (AR)OKEven: OK / Odd: PG PPSE projectPG PPS-MEGA project
3125NEED DC (AR)OKPG PPS-MEGA project
3267NEED DC (AR)OKEven: OK / Odd: PG PPSE projectPG PPS-MEGA project
3375NEED DC (AR)OKPG PPS-MEGA project
19683To be determinedUntested
                             

Legend

OKAll tests in this range has at least two matching residues, calculated by two different users. The range is considered completed.
NEED DC (AR)This range was tested on Boinc in Adaptive Replication mode. Some tests has only one residue from single user. The range must be partially double-checked. An average error rate in these areas is about 0.1%.
NEED DC (PrpNet)This range was tested on PrpNet server. Only one residue per test, no error checking at all. The range must be completely double-checked. An average error rate is around 1-2%, but may vary unpredictably depending on percentage of participated faulty hosts.
PG ProjectThis range is currently being tested in one of PrimeGrid projects.
DC in progressThis range is currently being double-checked on this server ("LLR2 testing" project).
Even / OddThis range has different status for odd and even N (DIV PrimeGrid project tested only odd or only even N for some K).

History

2021-10-15: Page created.

Main page · Your account · Message boards


Copyright © 2021 'stream' with help of PrimeGrid community