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 people. 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

K450K
1M
1.422M
1.65M
2M
2.41M
3M
3.322M
3.486M
3.64M
4M
4.5M
5M
5.5M
6M
9M
10M
3OK up to 20M
5 … 7OKUntested
9OKPG PPS projectEven: Untested / Odd: OKUntested
11 … 25OKUntested
27OKPG PPS projectEven: NEED DC (PrpNet) / Odd: OKNEED DC (PrpNet)
29 … 49OKUntested
51 … 99OKPG PPS projectUntested
101 … 119OKPG PPS projectUntested
121OKPG PPS projectNEED DC (PrpNet)
123 … 285OKPG PPS projectUntested
287 … 299OKUntested
301 … 391OKDC in progressOKUntested
393 … 557OKDC in progressOKUntested
559 … 739OKDC in progressOKUntested
741 … 1199OKDC in progressOKUntested
1201 … 9999OKNEED DC (AR)OKPG PPSE projectOKUntested
K's which were tested separately in PG DIV project
1323OKNEED DC (AR)OKEven: OK / Odd: PG PPSE projectOKUntested
2187OKNEED DC (AR)OKEven: OK / Odd: PG PPSE projectOKUntested
3125OKNEED DC (AR)OKUntested
3267OKNEED DC (AR)OKEven: OK / Odd: PG PPSE projectOKUntested
3375OKNEED DC (AR)OKUntested
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

2024-09-28: K = 1201 … 9999, N < 450K re-tested manually. 11 missed primes found by me and Christian Wallbaum, 16 additional primes found by Gary Gostin at prothsearch.com who duplicated part of the work.
2024-06-02: K ≤ 391, N = 4.5M … 5M finished and verified (PrimeGrid PPS project)
2024-02-14: K ≤ 557, N = 4M … 4.5M finished and verified (PrimeGrid PPS project)
2024-02-06: K = 301 … 1199, N = 1M … 2M DC finished (this server).
2023-11-09: PrimeGrid suspended PPS-MEGA project at N = 3.486M, fully testing range of K = 1201 … 9999, N = 3.322M … 3.486M.
2023-07-11: K ≤ 739, N = 3.64M … 4M finished and verified (PrimeGrid PPS project)
2023-01-05: K = 301 … 1199, N < 1M DC finished (this server).
2022-12-25: K = 3 (PrimeGrid "321" project, Proth part) fully verified up to N=18M, no problems found. The table will be periodically updated according to project progress without new history entries.
2022-11-24: K = 101 … 299, N < 2M DC finished (this server).
2022-08-19: K = 101 … 1199, N = 3M … 3.322M finished (PrimeGrid PPS Project) and verified. PrimeGrid started new PPS project for a complex range of K and N.
2022-05-15: K = 5 … 99, N < 2M DC finished (this server).
2022-03-15: K = 101 … 299, N = 2M … 3M DC finished (this server), finding a missed prime 281·22051865+1.
2022-02-02: K = 5 … 99, N = 2M … 3M DC finished (this server).
2021-10-15: Page created.
2021-05-28: Missed prime 879·2110075+1 found during manual DC of small numbers (K ≤ 1199, N < 500K).
2021-01-27: Missed prime 65·23369359+1 found in PPS-MEGA range (3.332M - 3.64M). This range was considered completed but it was discovered that a small range of N-values wasn't tested at all, hiding a prime.

Main page · Your account · Message boards


Copyright © 2024 'stream' with help of PrimeGrid community