PrimeGrid
Please visit donation page to help the project cover running costs for this month

Toggle Menu

Join PrimeGrid

Returning Participants

Community

Leader Boards

Results

Other

drummers-lowrise

Advanced search

Message boards : Proth Prime Search : How can we beat GIMPS

Author Message
Profile steveking
Send message
Joined: 22 May 16
Posts: 14
ID: 448042
Credit: 13,001,433
RAC: 0
PPS LLR Jade: Earned 10,000,000 credits (12,667,689)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Silver: Earned 100,000 credits (333,744)
Message 95394 - Posted: 1 Jun 2016 | 0:42:04 UTC

All primes end in 1 3 7 9. Is there some optimization PrimeGrid can do to reduce the cost function so that we are not checking "obvious" non primes? Geeeze!!

mackerelProject donor
Volunteer tester
Avatar
Send message
Joined: 2 Oct 08
Posts: 2214
ID: 29980
Credit: 334,817,604
RAC: 124,335
Discovered 2 mega primesEliminated 1 conjecture "k"Found 3 primes in the 2018 Tour de PrimesFound 1 mega prime in the 2018 Tour de PrimesFound 5 primes in the 2019 Tour de Primes321 LLR Turquoise: Earned 5,000,000 credits (7,218,911)Cullen LLR Turquoise: Earned 5,000,000 credits (5,149,818)ESP LLR Turquoise: Earned 5,000,000 credits (6,454,573)Generalized Cullen/Woodall LLR Turquoise: Earned 5,000,000 credits (5,122,074)PPS LLR Sapphire: Earned 20,000,000 credits (48,586,872)PSP LLR Jade: Earned 10,000,000 credits (10,128,604)SoB LLR Jade: Earned 10,000,000 credits (17,319,914)SR5 LLR Jade: Earned 10,000,000 credits (18,479,395)SGS LLR Turquoise: Earned 5,000,000 credits (6,702,766)TPS LLR (retired) Bronze: Earned 10,000 credits (34,130)TRP LLR Jade: Earned 10,000,000 credits (15,154,737)Woodall LLR Turquoise: Earned 5,000,000 credits (5,715,464)321 Sieve Turquoise: Earned 5,000,000 credits (8,326,385)Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,383,853)Generalized Cullen/Woodall Sieve (suspended) Sapphire: Earned 20,000,000 credits (20,626,419)PPS Sieve Emerald: Earned 50,000,000 credits (74,140,875)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Ruby: Earned 2,000,000 credits (2,293,882)TRP Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,012,757)AP 26/27 Sapphire: Earned 20,000,000 credits (21,918,894)GFN Sapphire: Earned 20,000,000 credits (48,107,585)PSA Ruby: Earned 2,000,000 credits (2,939,755)
Message 95396 - Posted: 1 Jun 2016 | 7:58:31 UTC - in response to Message 95394.

Sieve already does remove a lot of candidates relatively quickly and easily.

Profile DaveProject donor
Avatar
Send message
Joined: 13 Feb 12
Posts: 2583
ID: 130544
Credit: 805,515,935
RAC: 340,682
Found 2 primes in the 2018 Tour de Primes321 LLR Turquoise: Earned 5,000,000 credits (5,008,573)Cullen LLR Turquoise: Earned 5,000,000 credits (5,005,909)ESP LLR Turquoise: Earned 5,000,000 credits (5,303,526)Generalized Cullen/Woodall LLR Turquoise: Earned 5,000,000 credits (5,202,873)PPS LLR Turquoise: Earned 5,000,000 credits (5,502,394)PSP LLR Turquoise: Earned 5,000,000 credits (5,021,564)SoB LLR Turquoise: Earned 5,000,000 credits (8,851,996)SR5 LLR Turquoise: Earned 5,000,000 credits (5,000,482)SGS LLR Turquoise: Earned 5,000,000 credits (5,000,035)TRP LLR Ruby: Earned 2,000,000 credits (4,196,756)Woodall LLR Ruby: Earned 2,000,000 credits (3,007,050)321 Sieve Ruby: Earned 2,000,000 credits (2,516,995)Cullen/Woodall Sieve (suspended) Silver: Earned 100,000 credits (268,250)Generalized Cullen/Woodall Sieve (suspended) Jade: Earned 10,000,000 credits (10,000,502)PPS Sieve Double Silver: Earned 200,000,000 credits (300,002,145)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Jade: Earned 10,000,000 credits (10,000,133)TRP Sieve (suspended) Jade: Earned 10,000,000 credits (10,000,970)AP 26/27 Double Bronze: Earned 100,000,000 credits (115,629,800)GFN Double Bronze: Earned 100,000,000 credits (100,000,025)PSA Double Silver: Earned 200,000,000 credits (200,000,001)
Message 95397 - Posted: 1 Jun 2016 | 8:27:04 UTC

Best thing I would think is to try manual sieving for n=22.

Profile Crun-chiProject donor
Volunteer tester
Avatar
Send message
Joined: 25 Nov 09
Posts: 2785
ID: 50683
Credit: 52,558,486
RAC: 770
Eliminated 1 conjecture "k"Found 1 prime in the 2018 Tour de PrimesFound 1 prime in the 2019 Tour de Primes321 LLR Silver: Earned 100,000 credits (229,492)Cullen LLR Silver: Earned 100,000 credits (110,733)PPS LLR Ruby: Earned 2,000,000 credits (2,982,840)PSP LLR Silver: Earned 100,000 credits (104,385)SoB LLR Silver: Earned 100,000 credits (106,117)SR5 LLR Silver: Earned 100,000 credits (139,802)SGS LLR Amethyst: Earned 1,000,000 credits (1,073,792)TRP LLR Silver: Earned 100,000 credits (122,712)Woodall LLR Silver: Earned 100,000 credits (122,944)321 Sieve Silver: Earned 100,000 credits (104,900)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (2,000,599)Generalized Cullen/Woodall Sieve (suspended) Gold: Earned 500,000 credits (515,556)PPS Sieve Jade: Earned 10,000,000 credits (11,343,583)TRP Sieve (suspended) Silver: Earned 100,000 credits (255,612)AP 26/27 Ruby: Earned 2,000,000 credits (2,575,874)GFN Sapphire: Earned 20,000,000 credits (23,247,434)PSA Turquoise: Earned 5,000,000 credits (7,522,050)
Message 95398 - Posted: 1 Jun 2016 | 8:30:00 UTC - in response to Message 95394.

All primes end in 1 3 7 9. Is there some optimization PrimeGrid can do to reduce the cost function so that we are not checking "obvious" non primes? Geeeze!!

Primegrid use sieve depth as we, as individual will never reach. So it reduce "checking" of "non"obvious non primes alot!
I will give you example: I now run my small project
My sieve ( I need to do LLR) has 42400 candidates. If I have sieve depth from Primegrid I will have to check only 33000 candidates.
Second , I sow you are new here, you are not find any prime. Primegrid is not for non patient persons.
And last, does you join for finding primes or for collecting points and badges?
I wish you luck, what ever your motive is!
____________
271643232^131072+1 GENERALIZED FERMAT :)
93*10^1029523-1 REPDIGIT PRIME
31*332^367560+1 CRUS PRIME
Proud member of team Aggie The Pew. Go Aggie!

Profile Michael GoetzProject donor
Volunteer moderator
Project administrator
Project scientist
Avatar
Send message
Joined: 21 Jan 10
Posts: 12944
ID: 53948
Credit: 195,830,945
RAC: 150,178
The "Shut up already!" badge:  This loud mouth has mansplained on the forums over 10 thousand times!  Sheesh!!!Discovered the World's First GFN-19 prime!!!Discovered 1 mega primeFound 1 prime in the 2018 Tour de PrimesFound 1 prime in the 2019 Tour de Primes321 LLR Ruby: Earned 2,000,000 credits (2,085,897)Cullen LLR Ruby: Earned 2,000,000 credits (2,005,249)ESP LLR Turquoise: Earned 5,000,000 credits (5,009,577)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,145,754)PPS LLR Turquoise: Earned 5,000,000 credits (6,847,254)PSP LLR Ruby: Earned 2,000,000 credits (2,632,269)SoB LLR Sapphire: Earned 20,000,000 credits (34,221,148)SR5 LLR Turquoise: Earned 5,000,000 credits (8,293,415)SGS LLR Ruby: Earned 2,000,000 credits (2,012,222)TRP LLR Ruby: Earned 2,000,000 credits (2,737,347)Woodall LLR Ruby: Earned 2,000,000 credits (2,195,123)321 Sieve Turquoise: Earned 5,000,000 credits (5,046,112)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,170,256)Generalized Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,059,304)PPS Sieve Sapphire: Earned 20,000,000 credits (20,110,788)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,035,522)TRP Sieve (suspended) Ruby: Earned 2,000,000 credits (2,051,121)AP 26/27 Jade: Earned 10,000,000 credits (10,114,260)GFN Emerald: Earned 50,000,000 credits (65,656,284)PSA Jade: Earned 10,000,000 credits (12,404,447)
Message 95399 - Posted: 1 Jun 2016 | 10:23:14 UTC - in response to Message 95397.

Best thing I would think is to try manual sieving for n=22.


GIMPS is currently searching numbers larger than anything PrimeGrid is searching, including n=22. Sieving n=22 will not help.
____________
Please do not PM me with support questions. Ask on the forums instead. Thank you!

My lucky number is 75898524288+1

Profile JeppeSNProject donor
Send message
Joined: 5 Apr 14
Posts: 947
ID: 306875
Credit: 11,033,882
RAC: 7,943
321 LLR Silver: Earned 100,000 credits (285,114)Cullen LLR Bronze: Earned 10,000 credits (98,851)ESP LLR Silver: Earned 100,000 credits (139,922)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (35,236)PPS LLR Ruby: Earned 2,000,000 credits (2,424,942)SoB LLR Silver: Earned 100,000 credits (237,390)SR5 LLR Bronze: Earned 10,000 credits (16,010)TRP LLR Bronze: Earned 10,000 credits (71,060)Woodall LLR Silver: Earned 100,000 credits (109,455)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
Message 95407 - Posted: 1 Jun 2016 | 15:29:33 UTC - in response to Message 95394.

All primes end in 1 3 7 9.


When you sieve to p=2, you remove all candidates ending in 0,2,4,6,8. And when you sieve to p=5, you remove candidates ending in 5 as well.

/JeppeSN

Profile Rafael
Volunteer tester
Avatar
Send message
Joined: 22 Oct 14
Posts: 853
ID: 370496
Credit: 290,354,402
RAC: 51,093
321 LLR Turquoise: Earned 5,000,000 credits (5,777,242)Cullen LLR Turquoise: Earned 5,000,000 credits (5,592,227)ESP LLR Turquoise: Earned 5,000,000 credits (5,243,442)Generalized Cullen/Woodall LLR Turquoise: Earned 5,000,000 credits (5,036,673)PPS LLR Turquoise: Earned 5,000,000 credits (6,156,546)PSP LLR Turquoise: Earned 5,000,000 credits (5,169,383)SoB LLR Turquoise: Earned 5,000,000 credits (5,521,831)SR5 LLR Turquoise: Earned 5,000,000 credits (5,301,780)SGS LLR Turquoise: Earned 5,000,000 credits (5,069,139)TRP LLR Turquoise: Earned 5,000,000 credits (5,007,966)Woodall LLR Turquoise: Earned 5,000,000 credits (5,006,951)321 Sieve Gold: Earned 500,000 credits (869,696)Generalized Cullen/Woodall Sieve (suspended) Jade: Earned 10,000,000 credits (10,037,204)PPS Sieve Jade: Earned 10,000,000 credits (10,305,147)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Ruby: Earned 2,000,000 credits (2,000,053)TRP Sieve (suspended) Ruby: Earned 2,000,000 credits (2,030,160)AP 26/27 Jade: Earned 10,000,000 credits (10,253,048)GFN Sapphire: Earned 20,000,000 credits (25,217,853)PSA Double Bronze: Earned 100,000,000 credits (170,758,062)
Message 95408 - Posted: 1 Jun 2016 | 15:36:19 UTC - in response to Message 95399.

GIMPS is currently searching numbers larger than anything PrimeGrid is searching, including n=22. Sieving n=22 will not help.

The "GFN22-WR" dream (an analogy to GFN17-MEGA) would be much less of a distant dream if n=22 was properly sieved, don't you agree?

Or we could go crazy and start sieving n=23.


Not that any of those seem really likely to me, at least not within the spam of the next few years. But who knows, maybe in the future...

Profile Michael GoetzProject donor
Volunteer moderator
Project administrator
Project scientist
Avatar
Send message
Joined: 21 Jan 10
Posts: 12944
ID: 53948
Credit: 195,830,945
RAC: 150,178
The "Shut up already!" badge:  This loud mouth has mansplained on the forums over 10 thousand times!  Sheesh!!!Discovered the World's First GFN-19 prime!!!Discovered 1 mega primeFound 1 prime in the 2018 Tour de PrimesFound 1 prime in the 2019 Tour de Primes321 LLR Ruby: Earned 2,000,000 credits (2,085,897)Cullen LLR Ruby: Earned 2,000,000 credits (2,005,249)ESP LLR Turquoise: Earned 5,000,000 credits (5,009,577)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,145,754)PPS LLR Turquoise: Earned 5,000,000 credits (6,847,254)PSP LLR Ruby: Earned 2,000,000 credits (2,632,269)SoB LLR Sapphire: Earned 20,000,000 credits (34,221,148)SR5 LLR Turquoise: Earned 5,000,000 credits (8,293,415)SGS LLR Ruby: Earned 2,000,000 credits (2,012,222)TRP LLR Ruby: Earned 2,000,000 credits (2,737,347)Woodall LLR Ruby: Earned 2,000,000 credits (2,195,123)321 Sieve Turquoise: Earned 5,000,000 credits (5,046,112)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,170,256)Generalized Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,059,304)PPS Sieve Sapphire: Earned 20,000,000 credits (20,110,788)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,035,522)TRP Sieve (suspended) Ruby: Earned 2,000,000 credits (2,051,121)AP 26/27 Jade: Earned 10,000,000 credits (10,114,260)GFN Emerald: Earned 50,000,000 credits (65,656,284)PSA Jade: Earned 10,000,000 credits (12,404,447)
Message 95415 - Posted: 1 Jun 2016 | 17:19:42 UTC - in response to Message 95408.
Last modified: 1 Jun 2016 | 17:22:29 UTC

GIMPS is currently searching numbers larger than anything PrimeGrid is searching, including n=22. Sieving n=22 will not help.

The "GFN22-WR" dream (an analogy to GFN17-MEGA) would be much less of a distant dream if n=22 was properly sieved, don't you agree?

Or we could go crazy and start sieving n=23.


Not that any of those seem really likely to me, at least not within the spam of the next few years. But who knows, maybe in the future...


The "dream" of finding the world's largest known prime with the GFN22 search ended when the most recent Mersenne prime was found by GIMPS. That latest Mersenne is, and always will be, beyond the range of the GFN22 search due to the fact that the GFN searches increment B while the Mersenne search increments N. No amount of sieving will change that. Besides, 22 is exceptionally well sieved to a much higher level than the other ranges.

"Going crazy" and sieving/searching n=23 is a possibility, but the odds are even worse for n=23 than they were for n=22.
____________
Please do not PM me with support questions. Ask on the forums instead. Thank you!

My lucky number is 75898524288+1

Profile steveking
Send message
Joined: 22 May 16
Posts: 14
ID: 448042
Credit: 13,001,433
RAC: 0
PPS LLR Jade: Earned 10,000,000 credits (12,667,689)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Silver: Earned 100,000 credits (333,744)
Message 95425 - Posted: 2 Jun 2016 | 1:01:51 UTC - in response to Message 95398.

All primes end in 1 3 7 9. Is there some optimization PrimeGrid can do to reduce the cost function so that we are not checking "obvious" non primes? Geeeze!!

Primegrid use sieve depth as we, as individual will never reach. So it reduce "checking" of "non"obvious non primes alot!
I will give you example: I now run my small project
My sieve ( I need to do LLR) has 42400 candidates. If I have sieve depth from Primegrid I will have to check only 33000 candidates.
Second , I sow you are new here, you are not find any prime. Primegrid is not for non patient persons.
And last, does you join for finding primes or for collecting points and badges?
I wish you luck, what ever your motive is!



Very sorry to give you impression that I am impatient, I am not. I usually run Rosetta in which tasks take longer than Proth. I'm interested in finding Primes. To me number crucnching should be much faster than Protein Folding... which it is. I just thought number crunching would be alot faster. But I am okay with that. I hope my perceived impatience will not bother you. :)

Profile Rafael
Volunteer tester
Avatar
Send message
Joined: 22 Oct 14
Posts: 853
ID: 370496
Credit: 290,354,402
RAC: 51,093
321 LLR Turquoise: Earned 5,000,000 credits (5,777,242)Cullen LLR Turquoise: Earned 5,000,000 credits (5,592,227)ESP LLR Turquoise: Earned 5,000,000 credits (5,243,442)Generalized Cullen/Woodall LLR Turquoise: Earned 5,000,000 credits (5,036,673)PPS LLR Turquoise: Earned 5,000,000 credits (6,156,546)PSP LLR Turquoise: Earned 5,000,000 credits (5,169,383)SoB LLR Turquoise: Earned 5,000,000 credits (5,521,831)SR5 LLR Turquoise: Earned 5,000,000 credits (5,301,780)SGS LLR Turquoise: Earned 5,000,000 credits (5,069,139)TRP LLR Turquoise: Earned 5,000,000 credits (5,007,966)Woodall LLR Turquoise: Earned 5,000,000 credits (5,006,951)321 Sieve Gold: Earned 500,000 credits (869,696)Generalized Cullen/Woodall Sieve (suspended) Jade: Earned 10,000,000 credits (10,037,204)PPS Sieve Jade: Earned 10,000,000 credits (10,305,147)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Ruby: Earned 2,000,000 credits (2,000,053)TRP Sieve (suspended) Ruby: Earned 2,000,000 credits (2,030,160)AP 26/27 Jade: Earned 10,000,000 credits (10,253,048)GFN Sapphire: Earned 20,000,000 credits (25,217,853)PSA Double Bronze: Earned 100,000,000 credits (170,758,062)
Message 95426 - Posted: 2 Jun 2016 | 1:31:09 UTC - in response to Message 95425.

Very sorry to give you impression that I am impatient, I am not. I usually run Rosetta in which tasks take longer than Proth. I'm interested in finding Primes. To me number crucnching should be much faster than Protein Folding... which it is. I just thought number crunching would be alot faster. But I am okay with that. I hope my perceived impatience will not bother you. :)

Depends on the type of number being crunch. The PPS searchs are the fastest ones available at PrimeGrid, the other one being SGS.

Try something like Cullen or Seventeen or Bust, and you'll see just how lengthy prime crunching can be...

Profile steveking
Send message
Joined: 22 May 16
Posts: 14
ID: 448042
Credit: 13,001,433
RAC: 0
PPS LLR Jade: Earned 10,000,000 credits (12,667,689)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Silver: Earned 100,000 credits (333,744)
Message 95427 - Posted: 2 Jun 2016 | 1:48:12 UTC - in response to Message 95426.

I'm good. I'll stay with Proth.

JimBProject donor
Volunteer moderator
Project administrator
Project developer
Send message
Joined: 4 Aug 11
Posts: 884
ID: 107307
Credit: 852,132,632
RAC: 120,469
321 LLR Ruby: Earned 2,000,000 credits (2,071,006)Cullen LLR Ruby: Earned 2,000,000 credits (4,831,475)ESP LLR Turquoise: Earned 5,000,000 credits (5,064,082)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,589,971)PPS LLR Ruby: Earned 2,000,000 credits (2,668,927)PSP LLR Turquoise: Earned 5,000,000 credits (5,013,650)SoB LLR Sapphire: Earned 20,000,000 credits (42,020,807)SR5 LLR Jade: Earned 10,000,000 credits (10,987,079)SGS LLR Ruby: Earned 2,000,000 credits (2,069,865)TRP LLR Ruby: Earned 2,000,000 credits (2,145,683)Woodall LLR Ruby: Earned 2,000,000 credits (2,595,228)321 Sieve Turquoise: Earned 5,000,000 credits (5,653,634)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,002,919)Generalized Cullen/Woodall Sieve (suspended) Sapphire: Earned 20,000,000 credits (20,005,451)PPS Sieve Emerald: Earned 50,000,000 credits (50,809,179)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Ruby: Earned 2,000,000 credits (2,341,676)TRP Sieve (suspended) Ruby: Earned 2,000,000 credits (2,070,804)AP 26/27 Jade: Earned 10,000,000 credits (10,742,251)GFN Sapphire: Earned 20,000,000 credits (31,494,612)PSA Double Gold: Earned 500,000,000 credits (642,957,383)
Message 95459 - Posted: 3 Jun 2016 | 12:15:21 UTC
Last modified: 3 Jun 2016 | 20:44:34 UTC

I figure maybe I should post an explanation of all this. I remember how incomprehensible it all was when I first joined.

For all the Prime Proth Search projects (PPS, PPSE, PPS Mega) we're looking at candidates (potential primes) of the form k*2^n+1 or to make it easier to see which operation is performed first: (k*(2^n))+1

* means multiplication where (at least when I was a kid) x was used.
3*5 = 15, 7*8 = 56, etc.

^ means exponentiation - raising a number to a power.
2^5 is 32 because 32 = 2*2*2*2*2 - two multiplied by itself five times.

k and n are always integers (whole numbers) and always greater than zero.

k is an odd number between 5 and 1199 (for PPS)
k is an odd number between 1201 and 9999 (for PPSE)
k is an odd number between 5 and 399 (for PPS MEGA)

k starts at 5 rather than 3 because all k=3 are tested in the 321 subproject.

PPS MEGA are really just PPS candidates that happen to have over 1 million digits because they have a larger n. k is only up to 399 so far because we don't yet need more candidates (the next batch will be k=401-499). When PPS reaches PPS MEGA territory we'll skip all the candidates already tested by PPS MEGA and at that time PPS MEGA will either change or end.

Why is k always odd? Let's say we're interested in 6*2^5+1. 6 = 2*3 and we could also write this candidate as 3*2^6+1. Either way the value is 193 (which is prime). By sticking to odd k values, we make sure that every candidate is tested only once. With an odd k we know that every combination of k and n create a unique candidate that isn't repeated anywhere else.

n started at 1 or 2, can be both odd or even, and just keeps getting larger.

So we're multiplying an odd number by an even number. That result is always even. We're then adding one, which means the candidate is always odd - never divisible by 2.

Before we ever think of testing a candidate for primality, we do sieving. You can think of sieving as dividing every candidate by some number. This number, called p, starts at 3 and ideally is always a prime number. Trying to divide by non-primes is just a waste of time. Even though I said "divide", we're really not interested in the answer (the quotient). We're just interested in the remainder. If the remainder is zero, the candidate is evenly divisible by whatever p value we're using. A prime is only divisible by 1 and itself, so any candidate where we have found some factor p is immediately eliminated. It will never have a primality test done on it because we've proven beyond a doubt that it is not prime.

As we sieve, the p value gets larger and larger. Small primes like 3, 5, 7, 11, 13, etc are eliminated immediately, long before sieving ever gets put on PrimeGrid. Early sieving generates so many factors so quickly that until recently we didn't even bother keeping the factors. It's faster to just run the sieving again (if it was ever needed) than to store gigabytes of factors. So early sieving produces what we call sieve files. That's a list of all the candidates that have not yet been eliminated.

By the way, while it takes time to test candidates against potential factors, verifying factors is very fast and easy. Each and every factor produced by sieving, no matter which project it's for, is tested at least twice to make sure it's really valid. It takes only a few minutes to test all the PPS Sieving factors produced in a month, so there's no reason not to test and retest them.

Early sieving is done on the computer(s) of someone behind the scenes at PrimeGrid. At one time Lennart did that, now I do. I will have sieved to p=10T (that's ten trillion or 10,000,000,000,000) before the PrimeGrid community starts further sieving. So any number that has a factor less then 10T has already been eliminated. While that might seem like a large number, it's really not. We sieve until it takes less time to primality test every remaining candidate than it does to eliminate them by further sieving. You can think of that as candidates fully tested per day vs candidates sieved out per day. When the first value is greater than the second value, we're done sieving.

Because we don't want to sieve an endless number of candidates at once, we sieve ranges of n. Initially I believe we sieved n=1-100K or 1-500K. These days for PPS projects we sieve three million n values at a time. Right now on BOINC we're sieving n=6M-9M which means 6,000,000-8,999,999. In the manual sieving we're doing n=9M-12M. You'll sometimes see that written as 9M <= n < 12M. For n values below 6M, we hit the optimal sieving level and don't currently sieve any further. For n under 3M we sieved to 100P. For n=3M-6M that optimal p value was 400P. P = Peta = 10^15, so 400P = 400,000,000,000,000,000. We sieved 3M-6M higher because those candidates are larger and take much more time for primality testing. So it was worth sieving for much longer. At some point when we've hit the optimal sieving level for n=6M-9M, we'll shift 9M-12M to BOINC and (probably) start manual sieving on n=12M-15M. But in truth, we won't be primality testing those in my lifetime unless some new much-faster code is invented. Right now, BOINC PPS sieving is around p=172P as you can see at http://www.primegrid.com/stats_pps_sieve.php. Any factor counts you see there are for factors found in the last hour. Once an hour all factors are swept into a file that's stored on the server (and automatically downloaded by me five minutes later). Those factors are kept forever.

You might wonder why we talk about PPS, PPSE and PPS Mega in the LLR projects while the sieving is sometimes called PPR Sieving. That's because we also sieve for candidates in the form of k*2^n-1. Those candidates are called Riesel numbers and it takes very little extra time to generate them. While we don't really use that sieving here except on the 321 project and the PRPNet k=27 and k=121 projects, we do make those sieves available for people outside of PrimeGrid. You can see all the Riesel sieves at http://www.primegrid.com/sieving/rsp. If you're so curious that you have to download one of them, please choose one of the smaller files in the bottom section. We get charged for every byte of download. Many of those candidates have already been tested, so please don't waste your time unless you first read the Riesel Prime Search forum on mersenneforum.org.

As you can see on the above download page, we produce one sieve file per 1M of n. Plus there are separate sieves for +1 (PPS) and -1 (RSP). That's because those sieves are so large. Factors produced are applied to all six sieve files covering that n range. Any given factor only affects one sieve file at most, of course.

Finally, PPS sieving is what's called datless sieving. Every candidate is tested without regard to any existing sieve file. On the GPU, this is actually much faster than only testing the remaining candidates. So a lot of factors are found for candidates that have already been eliminated. There's no statistics chart that shows the actual sieve removal rate for PPS sieving, but about 22-23% of factors found result in removals from the sieve. That's taken into account when we determine the optimal sieving point, as only sieve removals matter.

Eventually when we're done sieving, those sieve files become the lists of candidates loaded into the BOINC system to be LLR tested for primality. So you can see that we've eliminated the vast majority of the candidates (1/3 of them are divisible by 3) and we're primality testing the minimum practical number of them.

Profile Crun-chiProject donor
Volunteer tester
Avatar
Send message
Joined: 25 Nov 09
Posts: 2785
ID: 50683
Credit: 52,558,486
RAC: 770
Eliminated 1 conjecture "k"Found 1 prime in the 2018 Tour de PrimesFound 1 prime in the 2019 Tour de Primes321 LLR Silver: Earned 100,000 credits (229,492)Cullen LLR Silver: Earned 100,000 credits (110,733)PPS LLR Ruby: Earned 2,000,000 credits (2,982,840)PSP LLR Silver: Earned 100,000 credits (104,385)SoB LLR Silver: Earned 100,000 credits (106,117)SR5 LLR Silver: Earned 100,000 credits (139,802)SGS LLR Amethyst: Earned 1,000,000 credits (1,073,792)TRP LLR Silver: Earned 100,000 credits (122,712)Woodall LLR Silver: Earned 100,000 credits (122,944)321 Sieve Silver: Earned 100,000 credits (104,900)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (2,000,599)Generalized Cullen/Woodall Sieve (suspended) Gold: Earned 500,000 credits (515,556)PPS Sieve Jade: Earned 10,000,000 credits (11,343,583)TRP Sieve (suspended) Silver: Earned 100,000 credits (255,612)AP 26/27 Ruby: Earned 2,000,000 credits (2,575,874)GFN Sapphire: Earned 20,000,000 credits (23,247,434)PSA Turquoise: Earned 5,000,000 credits (7,522,050)
Message 95476 - Posted: 4 Jun 2016 | 7:45:25 UTC - in response to Message 95425.

Very sorry to give you impression that I am impatient, I am not. I usually run Rosetta in which tasks take longer than Proth. I'm interested in finding Primes. To me number crucnching should be much faster than Protein Folding... which it is. I just thought number crunching would be alot faster. But I am okay with that. I hope my perceived impatience will not bother you. :)


No, I am just a member of Primegrid as you are!
Also I temporary left Primegrid ( you can see on my RAC) because I wont to search outside "range" that Primegrid tested.
And that is all. I wish that you find many primes :)
____________
271643232^131072+1 GENERALIZED FERMAT :)
93*10^1029523-1 REPDIGIT PRIME
31*332^367560+1 CRUS PRIME
Proud member of team Aggie The Pew. Go Aggie!

Message boards : Proth Prime Search : How can we beat GIMPS

[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2019 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 1.55, 2.19, 2.39
Generated 22 Oct 2019 | 11:59:37 UTC