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 : Number crunching : Prime number search

Author Message
Profile DingoProject donor
Avatar
Send message
Joined: 11 Aug 05
Posts: 93
ID: 125
Credit: 281,276,525
RAC: 6,760
Discovered 1 mega primeFound 2 primes in the 2019 Tour de Primes321 LLR Ruby: Earned 2,000,000 credits (2,892,019)Cullen LLR Amethyst: Earned 1,000,000 credits (1,328,719)ESP LLR Ruby: Earned 2,000,000 credits (2,349,411)Generalized Cullen/Woodall LLR Amethyst: Earned 1,000,000 credits (1,121,078)PPS LLR Jade: Earned 10,000,000 credits (19,943,242)PSP LLR Amethyst: Earned 1,000,000 credits (1,000,448)SoB LLR Amethyst: Earned 1,000,000 credits (1,442,992)SR5 LLR Ruby: Earned 2,000,000 credits (2,067,841)SGS LLR Ruby: Earned 2,000,000 credits (2,812,125)TPS LLR (retired) Bronze: Earned 10,000 credits (53,832)TRP LLR Ruby: Earned 2,000,000 credits (3,862,908)Woodall LLR Ruby: Earned 2,000,000 credits (2,018,846)321 Sieve Ruby: Earned 2,000,000 credits (2,206,940)Cullen/Woodall Sieve (suspended) Silver: Earned 100,000 credits (112,575)Generalized Cullen/Woodall Sieve (suspended) Silver: Earned 100,000 credits (259,359)PPS Sieve Emerald: Earned 50,000,000 credits (68,648,682)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Gold: Earned 500,000 credits (556,604)TRP Sieve (suspended) Silver: Earned 100,000 credits (152,538)AP 26/27 Jade: Earned 10,000,000 credits (11,067,211)GFN Double Bronze: Earned 100,000,000 credits (119,818,915)PSA Sapphire: Earned 20,000,000 credits (31,982,658)
Message 38144 - Posted: 10 Jul 2011 | 6:26:14 UTC

Do the prime numbers that are found and published come from both the llr and sieve work units or just one of them ??
____________

Proud Founder of
Have a look at my WebCam
My best Prime 46776558131072+1

SiKTheGreatOne
Volunteer tester
Avatar
Send message
Joined: 20 Mar 08
Posts: 110
ID: 20411
Credit: 101,493,682
RAC: 0
321 LLR Bronze: Earned 10,000 credits (60,082)Cullen LLR Bronze: Earned 10,000 credits (15,423)ESP LLR Gold: Earned 500,000 credits (519,856)PPS LLR Gold: Earned 500,000 credits (526,520)PSP LLR Bronze: Earned 10,000 credits (24,206)SoB LLR Bronze: Earned 10,000 credits (14,422)SR5 LLR Gold: Earned 500,000 credits (518,356)SGS LLR Silver: Earned 100,000 credits (102,655)TPS LLR (retired) Bronze: Earned 10,000 credits (31,486)TRP LLR Bronze: Earned 10,000 credits (29,696)Woodall LLR Amethyst: Earned 1,000,000 credits (1,039,198)321 Sieve Amethyst: Earned 1,000,000 credits (1,020,771)Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (8,228,565)PPS Sieve Emerald: Earned 50,000,000 credits (84,579,993)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Ruby: Earned 2,000,000 credits (2,070,654)TRP Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,211,586)AP 26/27 Silver: Earned 100,000 credits (115,596)GFN Silver: Earned 100,000 credits (200,628)PSA Amethyst: Earned 1,000,000 credits (1,184,000)
Message 38145 - Posted: 10 Jul 2011 | 6:55:55 UTC

Prime numbers are only found from LLR applications. Factors are found from sieve applications. Factors are not prime and sieving helps by removing many candidates that are not prime. This helps because for an LLR task, the result is a prime or no prime, and sieving removes many of these no prime results. Anything that is not sieved must be LLR tested to determine if it is prime.
____________

Profile DingoProject donor
Avatar
Send message
Joined: 11 Aug 05
Posts: 93
ID: 125
Credit: 281,276,525
RAC: 6,760
Discovered 1 mega primeFound 2 primes in the 2019 Tour de Primes321 LLR Ruby: Earned 2,000,000 credits (2,892,019)Cullen LLR Amethyst: Earned 1,000,000 credits (1,328,719)ESP LLR Ruby: Earned 2,000,000 credits (2,349,411)Generalized Cullen/Woodall LLR Amethyst: Earned 1,000,000 credits (1,121,078)PPS LLR Jade: Earned 10,000,000 credits (19,943,242)PSP LLR Amethyst: Earned 1,000,000 credits (1,000,448)SoB LLR Amethyst: Earned 1,000,000 credits (1,442,992)SR5 LLR Ruby: Earned 2,000,000 credits (2,067,841)SGS LLR Ruby: Earned 2,000,000 credits (2,812,125)TPS LLR (retired) Bronze: Earned 10,000 credits (53,832)TRP LLR Ruby: Earned 2,000,000 credits (3,862,908)Woodall LLR Ruby: Earned 2,000,000 credits (2,018,846)321 Sieve Ruby: Earned 2,000,000 credits (2,206,940)Cullen/Woodall Sieve (suspended) Silver: Earned 100,000 credits (112,575)Generalized Cullen/Woodall Sieve (suspended) Silver: Earned 100,000 credits (259,359)PPS Sieve Emerald: Earned 50,000,000 credits (68,648,682)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Gold: Earned 500,000 credits (556,604)TRP Sieve (suspended) Silver: Earned 100,000 credits (152,538)AP 26/27 Jade: Earned 10,000,000 credits (11,067,211)GFN Double Bronze: Earned 100,000,000 credits (119,818,915)PSA Sapphire: Earned 20,000,000 credits (31,982,658)
Message 38165 - Posted: 10 Jul 2011 | 14:26:32 UTC

Thanks that clears it up. I wish there was a ATI Graphics app for a llr project !!


____________

Proud Founder of
Have a look at my WebCam
My best Prime 46776558131072+1

Ken_g6Project donor
Volunteer developer
Avatar
Send message
Joined: 4 Jul 06
Posts: 915
ID: 3110
Credit: 183,164,814
RAC: 4,009
Discovered 1 mega primeFound 2 primes in the 2018 Tour de PrimesFound 1 prime in the 2019 Tour de PrimesFound 1 prime in the 2020 Tour de Primes321 LLR Ruby: Earned 2,000,000 credits (2,010,094)Cullen LLR Ruby: Earned 2,000,000 credits (2,022,806)ESP LLR Amethyst: Earned 1,000,000 credits (1,193,202)Generalized Cullen/Woodall LLR Gold: Earned 500,000 credits (767,102)PPS LLR Jade: Earned 10,000,000 credits (17,537,174)PSP LLR Ruby: Earned 2,000,000 credits (4,060,731)SoB LLR Ruby: Earned 2,000,000 credits (3,860,053)SR5 LLR Ruby: Earned 2,000,000 credits (2,061,736)SGS LLR Amethyst: Earned 1,000,000 credits (1,923,102)TPS LLR (retired) Bronze: Earned 10,000 credits (19,376)TRP LLR Ruby: Earned 2,000,000 credits (2,520,745)Woodall LLR Ruby: Earned 2,000,000 credits (2,021,413)321 Sieve Ruby: Earned 2,000,000 credits (2,915,071)Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (8,584,236)Generalized Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (2,461,309)PPS Sieve Emerald: Earned 50,000,000 credits (83,501,701)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Silver: Earned 100,000 credits (352,129)TRP Sieve (suspended) Gold: Earned 500,000 credits (776,202)AP 26/27 Turquoise: Earned 5,000,000 credits (5,851,049)GFN Sapphire: Earned 20,000,000 credits (34,062,697)PSA Ruby: Earned 2,000,000 credits (4,154,617)
Message 38169 - Posted: 10 Jul 2011 | 16:55:27 UTC - in response to Message 38145.

Factors are not prime and sieving helps by removing many candidates that are not prime.

Factors are absolutely prime. They're just primes that are smaller than the candidates being tested; sieved factors are by far too small for the top 5000. Factored candidates are not prime.
____________

Profile DaveBProject donor
Avatar
Send message
Joined: 20 Jun 09
Posts: 351
ID: 42198
Credit: 11,898,570
RAC: 0
321 LLR Gold: Earned 500,000 credits (547,769)Cullen LLR Silver: Earned 100,000 credits (158,867)PPS LLR Silver: Earned 100,000 credits (162,534)PSP LLR Silver: Earned 100,000 credits (134,373)SoB LLR Gold: Earned 500,000 credits (510,012)SR5 LLR Silver: Earned 100,000 credits (266,757)SGS LLR Gold: Earned 500,000 credits (510,560)TRP LLR Silver: Earned 100,000 credits (242,439)Woodall LLR Gold: Earned 500,000 credits (508,989)321 Sieve Silver: Earned 100,000 credits (200,123)Cullen/Woodall Sieve (suspended) Silver: Earned 100,000 credits (229,801)PPS Sieve Ruby: Earned 2,000,000 credits (4,317,221)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Bronze: Earned 10,000 credits (21,147)TRP Sieve (suspended) Silver: Earned 100,000 credits (333,494)AP 26/27 Bronze: Earned 10,000 credits (24,117)GFN Ruby: Earned 2,000,000 credits (3,730,320)
Message 38177 - Posted: 10 Jul 2011 | 20:58:58 UTC

To clear this up a factor may be prime or composite. For example the factors of 12 are {[4, 3], [2, 6], [2, 2, 3]} [4. 3] and [2, 6] are sets of composite factors, [2, 2, 3] is the set of prime factors. If one or more of the factors in a set is composite the whole set is called composite.

Any composite number has only one set of prime factors, the sets of composite factors (if any exist) are formed by the possible combinations of products of two or more members of the set of prime factors.

In PG numbers are tested by a partial sieve to remove the easy to find factors quickly and only those which pass through that sieve need to be tested by the longer LLR process. The LLR process determines whether a number is prime or composite but, if it is composite it does not identify the factors.

The LLR process (to put it simply) splits the number into smaller parts in a way which can be tested to find out if the whole number is prime. The spiltting is called a binomial expansion.
____________
Member team AUSTRALIA
My lucky number is 9291*2^1085585+1

SiKTheGreatOne
Volunteer tester
Avatar
Send message
Joined: 20 Mar 08
Posts: 110
ID: 20411
Credit: 101,493,682
RAC: 0
321 LLR Bronze: Earned 10,000 credits (60,082)Cullen LLR Bronze: Earned 10,000 credits (15,423)ESP LLR Gold: Earned 500,000 credits (519,856)PPS LLR Gold: Earned 500,000 credits (526,520)PSP LLR Bronze: Earned 10,000 credits (24,206)SoB LLR Bronze: Earned 10,000 credits (14,422)SR5 LLR Gold: Earned 500,000 credits (518,356)SGS LLR Silver: Earned 100,000 credits (102,655)TPS LLR (retired) Bronze: Earned 10,000 credits (31,486)TRP LLR Bronze: Earned 10,000 credits (29,696)Woodall LLR Amethyst: Earned 1,000,000 credits (1,039,198)321 Sieve Amethyst: Earned 1,000,000 credits (1,020,771)Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (8,228,565)PPS Sieve Emerald: Earned 50,000,000 credits (84,579,993)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Ruby: Earned 2,000,000 credits (2,070,654)TRP Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,211,586)AP 26/27 Silver: Earned 100,000 credits (115,596)GFN Silver: Earned 100,000 credits (200,628)PSA Amethyst: Earned 1,000,000 credits (1,184,000)
Message 38182 - Posted: 11 Jul 2011 | 1:32:01 UTC

I stand corrected. Thanks for clearing that up guys.
____________

Profile Rick Reynolds
Avatar
Send message
Joined: 13 Aug 10
Posts: 7880
ID: 65483
Credit: 5,312,080,766
RAC: 66,236
Discovered 2 mega primesFound 2 primes in the 2018 Tour de PrimesFound 2 primes in the 2019 Tour de PrimesFound 12 primes in the 2020 Tour de Primes321 LLR Jade: Earned 10,000,000 credits (10,244,909)Cullen LLR Jade: Earned 10,000,000 credits (10,194,451)ESP LLR Turquoise: Earned 5,000,000 credits (5,174,327)Generalized Cullen/Woodall LLR Turquoise: Earned 5,000,000 credits (5,028,260)PPS LLR Emerald: Earned 50,000,000 credits (61,072,468)PSP LLR Turquoise: Earned 5,000,000 credits (5,151,448)SoB LLR Turquoise: Earned 5,000,000 credits (5,014,268)SR5 LLR Jade: Earned 10,000,000 credits (14,871,275)SGS LLR Turquoise: Earned 5,000,000 credits (7,860,522)TRP LLR Jade: Earned 10,000,000 credits (11,130,742)Woodall LLR Turquoise: Earned 5,000,000 credits (5,419,909)321 Sieve Double Bronze: Earned 100,000,000 credits (101,538,236)Cullen/Woodall Sieve (suspended) Double Bronze: Earned 100,000,000 credits (127,922,665)Generalized Cullen/Woodall Sieve (suspended) Sapphire: Earned 20,000,000 credits (30,984,158)PPS Sieve Double Ruby: Earned 2,000,000,000 credits (2,840,173,136)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Turquoise: Earned 5,000,000 credits (8,134,964)TRP Sieve (suspended) Turquoise: Earned 5,000,000 credits (7,013,696)AP 26/27 Double Silver: Earned 200,000,000 credits (276,723,135)GFN Double Silver: Earned 200,000,000 credits (323,467,712)PSA Double Amethyst: Earned 1,000,000,000 credits (1,370,700,486)
Message 38186 - Posted: 11 Jul 2011 | 14:11:34 UTC - in response to Message 38169.

Factors are not prime and sieving helps by removing many candidates that are not prime.

Factors are absolutely prime. They're just primes that are smaller than the candidates being tested; sieved factors are by far too small for the top 5000. Factored candidates are not prime.


Well this is very interesting news since I've always read where the sieve projects don't find primes and have read it many times.

Rick
____________
@AggieThePew

Iain BethuneProject donor
Honorary cruncher
Send message
Joined: 28 Jan 09
Posts: 1588
ID: 34775
Credit: 194,056,043
RAC: 0
321 LLR Gold: Earned 500,000 credits (597,175)Cullen LLR Amethyst: Earned 1,000,000 credits (1,355,381)ESP LLR Turquoise: Earned 5,000,000 credits (5,048,594)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,564,412)PPS LLR Amethyst: Earned 1,000,000 credits (1,025,115)PSP LLR Sapphire: Earned 20,000,000 credits (28,367,849)SoB LLR Jade: Earned 10,000,000 credits (16,215,329)SR5 LLR Turquoise: Earned 5,000,000 credits (5,189,992)SGS LLR Amethyst: Earned 1,000,000 credits (1,244,067)TRP LLR Turquoise: Earned 5,000,000 credits (5,169,405)Woodall LLR Amethyst: Earned 1,000,000 credits (1,070,956)321 Sieve Bronze: Earned 10,000 credits (20,003)Cullen/Woodall Sieve (suspended) Silver: Earned 100,000 credits (200,371)Generalized Cullen/Woodall Sieve (suspended) Jade: Earned 10,000,000 credits (11,645,025)PPS Sieve Turquoise: Earned 5,000,000 credits (7,536,532)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,017,144)TRP Sieve (suspended) Gold: Earned 500,000 credits (554,946)AP 26/27 Ruby: Earned 2,000,000 credits (3,577,848)GFN Emerald: Earned 50,000,000 credits (97,047,976)PSA Ruby: Earned 2,000,000 credits (4,606,694)
Message 38190 - Posted: 11 Jul 2011 | 15:19:24 UTC - in response to Message 38186.
Last modified: 11 Jul 2011 | 15:20:15 UTC

Yes that's correct - the way a sieve works is to take a range of very large numbers (which may be prime or not, we don't know), and then use a range of small known primes to see if they divide any of the large numbers. If one of the small primes divides one of the large numbers being tested, the small prime is said to be a factor of one of the large numbers, and therefore the large number is composite (i.e. it has factors -> it is not prime), and the process iterates along. At the end, we have left a bunch of large numbers which are composites, and a bunch which are still unknown. These remaining numbers have passed the sieve and must then be primality tested by a method such as LLR to determine if they are prime or not.

The post above is correct. Sieves don't find new primes, but they do use small primes to disprove the primality of larger numbers. Hope that's clearer than mud!

Cheers

- Iain
____________
Twitter: IainBethune
Proud member of team "Aggie The Pew". Go Aggie!
3073428256125*2^1290000-1 is Prime!

Profile Rick Reynolds
Avatar
Send message
Joined: 13 Aug 10
Posts: 7880
ID: 65483
Credit: 5,312,080,766
RAC: 66,236
Discovered 2 mega primesFound 2 primes in the 2018 Tour de PrimesFound 2 primes in the 2019 Tour de PrimesFound 12 primes in the 2020 Tour de Primes321 LLR Jade: Earned 10,000,000 credits (10,244,909)Cullen LLR Jade: Earned 10,000,000 credits (10,194,451)ESP LLR Turquoise: Earned 5,000,000 credits (5,174,327)Generalized Cullen/Woodall LLR Turquoise: Earned 5,000,000 credits (5,028,260)PPS LLR Emerald: Earned 50,000,000 credits (61,072,468)PSP LLR Turquoise: Earned 5,000,000 credits (5,151,448)SoB LLR Turquoise: Earned 5,000,000 credits (5,014,268)SR5 LLR Jade: Earned 10,000,000 credits (14,871,275)SGS LLR Turquoise: Earned 5,000,000 credits (7,860,522)TRP LLR Jade: Earned 10,000,000 credits (11,130,742)Woodall LLR Turquoise: Earned 5,000,000 credits (5,419,909)321 Sieve Double Bronze: Earned 100,000,000 credits (101,538,236)Cullen/Woodall Sieve (suspended) Double Bronze: Earned 100,000,000 credits (127,922,665)Generalized Cullen/Woodall Sieve (suspended) Sapphire: Earned 20,000,000 credits (30,984,158)PPS Sieve Double Ruby: Earned 2,000,000,000 credits (2,840,173,136)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Turquoise: Earned 5,000,000 credits (8,134,964)TRP Sieve (suspended) Turquoise: Earned 5,000,000 credits (7,013,696)AP 26/27 Double Silver: Earned 200,000,000 credits (276,723,135)GFN Double Silver: Earned 200,000,000 credits (323,467,712)PSA Double Amethyst: Earned 1,000,000,000 credits (1,370,700,486)
Message 38191 - Posted: 11 Jul 2011 | 15:26:22 UTC - in response to Message 38190.
Last modified: 11 Jul 2011 | 15:31:18 UTC

Yes that's correct - the way a sieve works is to take a range of very large numbers (which may be prime or not, we don't know), and then use a range of small known primes to see if they divide any of the large numbers. If one of the small primes divides one of the large numbers being tested, the small prime is said to be a factor of one of the large numbers, and therefore the large number is composite (i.e. it has factors -> it is not prime), and the process iterates along. At the end, we have left a bunch of large numbers which are composites, and a bunch which are still unknown. These remaining numbers have passed the sieve and must then be primality tested by a method such as LLR to determine if they are prime or not.

The post above is correct. Sieves don't find new primes, but they do use small primes to disprove the primality of larger numbers. Hope that's clearer than mud!

Cheers

- Iain


Question, when running either pps sieve or gcw sieve and it shows in pg that a factor has been found.. that reported factor is a small prime? Reason I ask is that the pps sieve project returns a lot of factors. I guess where I'm confused is that apparently real primes are being reported as factors but those have already been proven to be primes ?

Question 2, if what you explained is true, are the small primes reused and if so reported as factors and if found to be another factor of a prime reported more than once?
____________
@AggieThePew

Profile Michael GoetzProject donor
Volunteer moderator
Project administrator
Avatar
Send message
Joined: 21 Jan 10
Posts: 13513
ID: 53948
Credit: 236,922,854
RAC: 3,199
Found 5 primes in the 2021 Tour de PrimesFound 5 mega primes in the 2021 Tour de PrimesThe "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 6 mega primesFound 1 prime in the 2018 Tour de PrimesFound 1 prime in the 2019 Tour de PrimesFound 1 prime in the 2020 Tour de Primes321 LLR Ruby: Earned 2,000,000 credits (2,822,730)Cullen LLR Ruby: Earned 2,000,000 credits (3,624,591)ESP LLR Turquoise: Earned 5,000,000 credits (5,021,269)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,145,754)PPS LLR Jade: Earned 10,000,000 credits (16,008,485)PSP LLR Turquoise: Earned 5,000,000 credits (5,197,957)SoB LLR Sapphire: Earned 20,000,000 credits (34,291,181)SR5 LLR Jade: Earned 10,000,000 credits (10,007,110)SGS LLR Ruby: Earned 2,000,000 credits (3,252,256)TRP LLR Turquoise: Earned 5,000,000 credits (5,084,329)Woodall LLR Ruby: Earned 2,000,000 credits (2,911,985)321 Sieve Jade: Earned 10,000,000 credits (10,061,196)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 (22,885,121)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,118,303)GFN Emerald: Earned 50,000,000 credits (76,733,355)PSA Jade: Earned 10,000,000 credits (12,445,029)
Message 38194 - Posted: 11 Jul 2011 | 15:42:42 UTC - in response to Message 38191.

Question, when running either pps sieve or gcw sieve and it shows in pg that a factor has been found.. that reported factor is a small prime? Reason I ask is that the pps sieve project returns a lot of factors. I guess where I'm confused is that apparently real primes are being reported as factors but those have already been proven to be primes ?


IIRC, this sieve doesn't use a 'sieve file' because of limitations of running on a GPU. (The sieve file for PPS is HUGE and wouldn't fit in the vast majority of GPU cards; it would probably need a card with 2 gig of video ram.) Without a sieve file, the program will keep finding the same factors over and over. Other sieves, with a sieve file, don't re-report factors that have been found previously. That's why you see a lot of factors found by PPS sieve. For PPS, it's more efficient to take full advantage of the GPU's power and simply correlate the duplicate factors on the server.

BTW, it's not so much the factor (the small prime) that's important here -- it's the composite number that it is a factor of which is important. That large composite number, once determined by the sieve to be composite, no longer needs to be LLR'd to check for primality; we know it's not prime. That's the whole point of the sieve, to quickly and easily determine that some of the candidates we want to test are composite. This saves a lot of LLR computing time.
____________
My lucky number is 75898524288+1

Profile Rick Reynolds
Avatar
Send message
Joined: 13 Aug 10
Posts: 7880
ID: 65483
Credit: 5,312,080,766
RAC: 66,236
Discovered 2 mega primesFound 2 primes in the 2018 Tour de PrimesFound 2 primes in the 2019 Tour de PrimesFound 12 primes in the 2020 Tour de Primes321 LLR Jade: Earned 10,000,000 credits (10,244,909)Cullen LLR Jade: Earned 10,000,000 credits (10,194,451)ESP LLR Turquoise: Earned 5,000,000 credits (5,174,327)Generalized Cullen/Woodall LLR Turquoise: Earned 5,000,000 credits (5,028,260)PPS LLR Emerald: Earned 50,000,000 credits (61,072,468)PSP LLR Turquoise: Earned 5,000,000 credits (5,151,448)SoB LLR Turquoise: Earned 5,000,000 credits (5,014,268)SR5 LLR Jade: Earned 10,000,000 credits (14,871,275)SGS LLR Turquoise: Earned 5,000,000 credits (7,860,522)TRP LLR Jade: Earned 10,000,000 credits (11,130,742)Woodall LLR Turquoise: Earned 5,000,000 credits (5,419,909)321 Sieve Double Bronze: Earned 100,000,000 credits (101,538,236)Cullen/Woodall Sieve (suspended) Double Bronze: Earned 100,000,000 credits (127,922,665)Generalized Cullen/Woodall Sieve (suspended) Sapphire: Earned 20,000,000 credits (30,984,158)PPS Sieve Double Ruby: Earned 2,000,000,000 credits (2,840,173,136)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Turquoise: Earned 5,000,000 credits (8,134,964)TRP Sieve (suspended) Turquoise: Earned 5,000,000 credits (7,013,696)AP 26/27 Double Silver: Earned 200,000,000 credits (276,723,135)GFN Double Silver: Earned 200,000,000 credits (323,467,712)PSA Double Amethyst: Earned 1,000,000,000 credits (1,370,700,486)
Message 38195 - Posted: 11 Jul 2011 | 15:50:45 UTC - in response to Message 38194.
Last modified: 11 Jul 2011 | 15:52:07 UTC

IIRC, this sieve doesn't use a 'sieve file' because of limitations of running on a GPU. (The sieve file for PPS is HUGE and wouldn't fit in the vast majority of GPU cards; it would probably need a card with 2 gig of video ram.) Without a sieve file, the program will keep finding the same factors over and over. Other sieves, with a sieve file, don't re-report factors that have been found previously. That's why you see a lot of factors found by PPS sieve. For PPS, it's more efficient to take full advantage of the GPU's power and simply correlate the duplicate factors on the server.

BTW, it's not so much the factor (the small prime) that's important here -- it's the composite number that it is a factor of which is important. That large composite number, once determined by the sieve to be composite, no longer needs to be LLR'd to check for primality; we know it's not prime. That's the whole point of the sieve, to quickly and easily determine that some of the candidates we want to test are composite. This saves a lot of LLR computing time.


That makes sense but then we are now back to the main question. A sieve project is using known primes to determine if a number is a composite, what happens if it's determined not to be a composite? It's retested with the llr and if found to be prime then in essence the sieve did find a prime or am I missing something. If that is true then shouldn't the very first original test count somewhere as a prime finder?
____________
@AggieThePew

Iain BethuneProject donor
Honorary cruncher
Send message
Joined: 28 Jan 09
Posts: 1588
ID: 34775
Credit: 194,056,043
RAC: 0
321 LLR Gold: Earned 500,000 credits (597,175)Cullen LLR Amethyst: Earned 1,000,000 credits (1,355,381)ESP LLR Turquoise: Earned 5,000,000 credits (5,048,594)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,564,412)PPS LLR Amethyst: Earned 1,000,000 credits (1,025,115)PSP LLR Sapphire: Earned 20,000,000 credits (28,367,849)SoB LLR Jade: Earned 10,000,000 credits (16,215,329)SR5 LLR Turquoise: Earned 5,000,000 credits (5,189,992)SGS LLR Amethyst: Earned 1,000,000 credits (1,244,067)TRP LLR Turquoise: Earned 5,000,000 credits (5,169,405)Woodall LLR Amethyst: Earned 1,000,000 credits (1,070,956)321 Sieve Bronze: Earned 10,000 credits (20,003)Cullen/Woodall Sieve (suspended) Silver: Earned 100,000 credits (200,371)Generalized Cullen/Woodall Sieve (suspended) Jade: Earned 10,000,000 credits (11,645,025)PPS Sieve Turquoise: Earned 5,000,000 credits (7,536,532)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,017,144)TRP Sieve (suspended) Gold: Earned 500,000 credits (554,946)AP 26/27 Ruby: Earned 2,000,000 credits (3,577,848)GFN Emerald: Earned 50,000,000 credits (97,047,976)PSA Ruby: Earned 2,000,000 credits (4,606,694)
Message 38196 - Posted: 11 Jul 2011 | 15:57:34 UTC - in response to Message 38195.
Last modified: 11 Jul 2011 | 15:59:57 UTC

I see what you mean now - if you look at an entry on the top5000 (e.g. for a recent 321 mega prime), you see credit to both the Sieve and Primality test program (LLR):

1. Michael Herder, discoverer
2. PrimeGrid, et al.
3. Srsieve, sieving program developed by Geoff Reynolds
4. LLR, primality program developed by Jean Penné

But the sieve itself did not find the prime - many (most) numbers that pass through the sieve are found to b composites by the LLR test - it's just that at some point running more and more sieves becomes more expensive than just running LLR tests against the remaining candidates.

If one sieved a large candidate number (call it N), using all the small primes up to sqrt(N) then one would indeed prove it prime (or not) via a sieve, but this would take much longer than just sieving to a depth much smaller than N, then LLR testing if the number was still not proven to be composite by this point.

- Iain
____________
Twitter: IainBethune
Proud member of team "Aggie The Pew". Go Aggie!
3073428256125*2^1290000-1 is Prime!

Profile Rick Reynolds
Avatar
Send message
Joined: 13 Aug 10
Posts: 7880
ID: 65483
Credit: 5,312,080,766
RAC: 66,236
Discovered 2 mega primesFound 2 primes in the 2018 Tour de PrimesFound 2 primes in the 2019 Tour de PrimesFound 12 primes in the 2020 Tour de Primes321 LLR Jade: Earned 10,000,000 credits (10,244,909)Cullen LLR Jade: Earned 10,000,000 credits (10,194,451)ESP LLR Turquoise: Earned 5,000,000 credits (5,174,327)Generalized Cullen/Woodall LLR Turquoise: Earned 5,000,000 credits (5,028,260)PPS LLR Emerald: Earned 50,000,000 credits (61,072,468)PSP LLR Turquoise: Earned 5,000,000 credits (5,151,448)SoB LLR Turquoise: Earned 5,000,000 credits (5,014,268)SR5 LLR Jade: Earned 10,000,000 credits (14,871,275)SGS LLR Turquoise: Earned 5,000,000 credits (7,860,522)TRP LLR Jade: Earned 10,000,000 credits (11,130,742)Woodall LLR Turquoise: Earned 5,000,000 credits (5,419,909)321 Sieve Double Bronze: Earned 100,000,000 credits (101,538,236)Cullen/Woodall Sieve (suspended) Double Bronze: Earned 100,000,000 credits (127,922,665)Generalized Cullen/Woodall Sieve (suspended) Sapphire: Earned 20,000,000 credits (30,984,158)PPS Sieve Double Ruby: Earned 2,000,000,000 credits (2,840,173,136)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Turquoise: Earned 5,000,000 credits (8,134,964)TRP Sieve (suspended) Turquoise: Earned 5,000,000 credits (7,013,696)AP 26/27 Double Silver: Earned 200,000,000 credits (276,723,135)GFN Double Silver: Earned 200,000,000 credits (323,467,712)PSA Double Amethyst: Earned 1,000,000,000 credits (1,370,700,486)
Message 38197 - Posted: 11 Jul 2011 | 16:04:03 UTC
Last modified: 11 Jul 2011 | 16:04:48 UTC

Think I understand. PG sieves use factors (primes as Ken stated) to help determine if a number is a composite. If a number somewhere in the magical depth of sieving is determined not to be a composite it's passed onto the llr for further testing.

At no point in the pg sieve projects will a "tested" number be reported as prime.

Is that correct?
____________
@AggieThePew

Profile Michael GoetzProject donor
Volunteer moderator
Project administrator
Avatar
Send message
Joined: 21 Jan 10
Posts: 13513
ID: 53948
Credit: 236,922,854
RAC: 3,199
Found 5 primes in the 2021 Tour de PrimesFound 5 mega primes in the 2021 Tour de PrimesThe "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 6 mega primesFound 1 prime in the 2018 Tour de PrimesFound 1 prime in the 2019 Tour de PrimesFound 1 prime in the 2020 Tour de Primes321 LLR Ruby: Earned 2,000,000 credits (2,822,730)Cullen LLR Ruby: Earned 2,000,000 credits (3,624,591)ESP LLR Turquoise: Earned 5,000,000 credits (5,021,269)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,145,754)PPS LLR Jade: Earned 10,000,000 credits (16,008,485)PSP LLR Turquoise: Earned 5,000,000 credits (5,197,957)SoB LLR Sapphire: Earned 20,000,000 credits (34,291,181)SR5 LLR Jade: Earned 10,000,000 credits (10,007,110)SGS LLR Ruby: Earned 2,000,000 credits (3,252,256)TRP LLR Turquoise: Earned 5,000,000 credits (5,084,329)Woodall LLR Ruby: Earned 2,000,000 credits (2,911,985)321 Sieve Jade: Earned 10,000,000 credits (10,061,196)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 (22,885,121)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,118,303)GFN Emerald: Earned 50,000,000 credits (76,733,355)PSA Jade: Earned 10,000,000 credits (12,445,029)
Message 38198 - Posted: 11 Jul 2011 | 16:11:32 UTC - in response to Message 38195.

That makes sense but then we are now back to the main question. A sieve project is using known primes to determine if a number is a composite, what happens if it's determined not to be a composite? It's retested with the llr and if found to be prime then in essence the sieve did find a prime or am I missing something. If that is true then shouldn't the very first original test count somewhere as a prime finder?


The highlighted portion, the essence of your question, can't happen. Your question makes the assumption that a candidate can be either composite or prime, but that is incorrect. A candidate can be either composite, prime, or not yet known.

Sieves can only prove that a candidate is composite. They can't prove that a number is NOT composite (and therefore prime.) So, after running the sieve, each candidate is either composite or unknown. They never get proven to be prime by the sieve.

In theory, if you run the sieve testing all primes up to the square root of the candidate, and none are found to be factors of the candidate, then you have proven the candidate to be prime. With the numbers we're testing, however, you will have died thousands (or millions or billions) of years before the sieve completes. It's not practical to test for primality in this fashion.

So, the process of finding large primes is broken into two steps. Step 1 is to run a sieve against a set of large candidate numbers. The sieve checks to see whether (comparatively) small primes are factors of any of the candidates. This rapidly eliminates a large number of the candidates in less time than it would take to test them with LLR. In step 2, the remaining candidates, all of which have not been proven composite, are then tested by LLR. LLR will go and prove them to be either prime or composite. Sieves, by comparison, can only prove them to be composite. If the sieve doesn't prove a candidate to be composite, then the status of the candidate remains unknown.
____________
My lucky number is 75898524288+1

Profile Michael GoetzProject donor
Volunteer moderator
Project administrator
Avatar
Send message
Joined: 21 Jan 10
Posts: 13513
ID: 53948
Credit: 236,922,854
RAC: 3,199
Found 5 primes in the 2021 Tour de PrimesFound 5 mega primes in the 2021 Tour de PrimesThe "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 6 mega primesFound 1 prime in the 2018 Tour de PrimesFound 1 prime in the 2019 Tour de PrimesFound 1 prime in the 2020 Tour de Primes321 LLR Ruby: Earned 2,000,000 credits (2,822,730)Cullen LLR Ruby: Earned 2,000,000 credits (3,624,591)ESP LLR Turquoise: Earned 5,000,000 credits (5,021,269)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,145,754)PPS LLR Jade: Earned 10,000,000 credits (16,008,485)PSP LLR Turquoise: Earned 5,000,000 credits (5,197,957)SoB LLR Sapphire: Earned 20,000,000 credits (34,291,181)SR5 LLR Jade: Earned 10,000,000 credits (10,007,110)SGS LLR Ruby: Earned 2,000,000 credits (3,252,256)TRP LLR Turquoise: Earned 5,000,000 credits (5,084,329)Woodall LLR Ruby: Earned 2,000,000 credits (2,911,985)321 Sieve Jade: Earned 10,000,000 credits (10,061,196)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 (22,885,121)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,118,303)GFN Emerald: Earned 50,000,000 credits (76,733,355)PSA Jade: Earned 10,000,000 credits (12,445,029)
Message 38199 - Posted: 11 Jul 2011 | 16:23:38 UTC - in response to Message 38197.

Think I understand. PG sieves use factors (primes as Ken stated) to help determine if a number is a composite. If a number somewhere in the magical depth of sieving is determined not to be a composite it's passed onto the llr for further testing.

At no point in the pg sieve projects will a "tested" number be reported as prime.

Is that correct?


Close, except that sieving doesn't ever determine that a candidate is not composite. All it can do is determine that it hadn't found a factor. That doesn't mean a factor doesn't exist. It just implies that the sieve didn't find one. Since the sieve won't, by design, test every possible factor, all that's proven is that this candidate's status is still unknown.

Here's an analogy. Your job is to pick 5 new astronauts. There's a hundred people standing in line in front of you. The first thing you do is get rid of the ones that are too short or too tall for the spaceship, which will only fit people between 5'6" and 5'10". Doing this immediately gets rid of 65 of your hundred candidates.

That doesn't prove the other 35 are qualified to be astronauts. It just proves the 65 you removed aren't. There's a lot more tests to be run, for education, skills, mental state, physical health, etc.

Same thing with prime sieves. They efficiently eliminate those numbers that can be easily proven to not be prime, but that doesn't tell you anything at all about the numbers that remain.
____________
My lucky number is 75898524288+1

Profile Rick Reynolds
Avatar
Send message
Joined: 13 Aug 10
Posts: 7880
ID: 65483
Credit: 5,312,080,766
RAC: 66,236
Discovered 2 mega primesFound 2 primes in the 2018 Tour de PrimesFound 2 primes in the 2019 Tour de PrimesFound 12 primes in the 2020 Tour de Primes321 LLR Jade: Earned 10,000,000 credits (10,244,909)Cullen LLR Jade: Earned 10,000,000 credits (10,194,451)ESP LLR Turquoise: Earned 5,000,000 credits (5,174,327)Generalized Cullen/Woodall LLR Turquoise: Earned 5,000,000 credits (5,028,260)PPS LLR Emerald: Earned 50,000,000 credits (61,072,468)PSP LLR Turquoise: Earned 5,000,000 credits (5,151,448)SoB LLR Turquoise: Earned 5,000,000 credits (5,014,268)SR5 LLR Jade: Earned 10,000,000 credits (14,871,275)SGS LLR Turquoise: Earned 5,000,000 credits (7,860,522)TRP LLR Jade: Earned 10,000,000 credits (11,130,742)Woodall LLR Turquoise: Earned 5,000,000 credits (5,419,909)321 Sieve Double Bronze: Earned 100,000,000 credits (101,538,236)Cullen/Woodall Sieve (suspended) Double Bronze: Earned 100,000,000 credits (127,922,665)Generalized Cullen/Woodall Sieve (suspended) Sapphire: Earned 20,000,000 credits (30,984,158)PPS Sieve Double Ruby: Earned 2,000,000,000 credits (2,840,173,136)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Turquoise: Earned 5,000,000 credits (8,134,964)TRP Sieve (suspended) Turquoise: Earned 5,000,000 credits (7,013,696)AP 26/27 Double Silver: Earned 200,000,000 credits (276,723,135)GFN Double Silver: Earned 200,000,000 credits (323,467,712)PSA Double Amethyst: Earned 1,000,000,000 credits (1,370,700,486)
Message 38202 - Posted: 11 Jul 2011 | 17:16:00 UTC

So, the answer to the question is, PG sieving does not find primes but does eliminate some numbers as candidates?
____________
@AggieThePew

Profile Michael GoetzProject donor
Volunteer moderator
Project administrator
Avatar
Send message
Joined: 21 Jan 10
Posts: 13513
ID: 53948
Credit: 236,922,854
RAC: 3,199
Found 5 primes in the 2021 Tour de PrimesFound 5 mega primes in the 2021 Tour de PrimesThe "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 6 mega primesFound 1 prime in the 2018 Tour de PrimesFound 1 prime in the 2019 Tour de PrimesFound 1 prime in the 2020 Tour de Primes321 LLR Ruby: Earned 2,000,000 credits (2,822,730)Cullen LLR Ruby: Earned 2,000,000 credits (3,624,591)ESP LLR Turquoise: Earned 5,000,000 credits (5,021,269)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,145,754)PPS LLR Jade: Earned 10,000,000 credits (16,008,485)PSP LLR Turquoise: Earned 5,000,000 credits (5,197,957)SoB LLR Sapphire: Earned 20,000,000 credits (34,291,181)SR5 LLR Jade: Earned 10,000,000 credits (10,007,110)SGS LLR Ruby: Earned 2,000,000 credits (3,252,256)TRP LLR Turquoise: Earned 5,000,000 credits (5,084,329)Woodall LLR Ruby: Earned 2,000,000 credits (2,911,985)321 Sieve Jade: Earned 10,000,000 credits (10,061,196)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 (22,885,121)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,118,303)GFN Emerald: Earned 50,000,000 credits (76,733,355)PSA Jade: Earned 10,000,000 credits (12,445,029)
Message 38217 - Posted: 11 Jul 2011 | 20:51:18 UTC - in response to Message 38202.

So, the answer to the question is, PG sieving does not find primes but does eliminate some numbers as candidates?


Correct.
____________
My lucky number is 75898524288+1

Brook HarsteProject donor
Avatar
Send message
Joined: 30 Nov 08
Posts: 1345
ID: 32401
Credit: 805,483,198
RAC: 0
Discovered 2 mega primesFound 1 prime in the 2019 Tour de Primes321 LLR Jade: Earned 10,000,000 credits (10,334,077)Cullen LLR Turquoise: Earned 5,000,000 credits (5,010,955)ESP LLR Turquoise: Earned 5,000,000 credits (7,439,418)Generalized Cullen/Woodall LLR Turquoise: Earned 5,000,000 credits (5,501,906)PPS LLR Sapphire: Earned 20,000,000 credits (26,697,006)PSP LLR Turquoise: Earned 5,000,000 credits (6,184,417)SoB LLR Jade: Earned 10,000,000 credits (12,120,365)SR5 LLR Turquoise: Earned 5,000,000 credits (9,234,440)SGS LLR Turquoise: Earned 5,000,000 credits (5,201,403)TRP LLR Turquoise: Earned 5,000,000 credits (5,628,223)Woodall LLR Turquoise: Earned 5,000,000 credits (5,061,985)321 Sieve Amethyst: Earned 1,000,000 credits (1,027,534)Cullen/Woodall Sieve (suspended) Jade: Earned 10,000,000 credits (17,370,919)Generalized Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,014,372)PPS Sieve Double Bronze: Earned 100,000,000 credits (129,430,775)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,083,315)TRP Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,629,248)AP 26/27 Emerald: Earned 50,000,000 credits (56,876,924)GFN Double Silver: Earned 200,000,000 credits (286,079,854)PSA Double Silver: Earned 200,000,000 credits (200,556,062)
Message 38218 - Posted: 11 Jul 2011 | 22:29:21 UTC - in response to Message 38217.

This tread should be gleaned and put into the wiki.
Lot's of good stuff I, and I'm sure others, did not know.
<big thumbs up>
____________

Profile DaveBProject donor
Avatar
Send message
Joined: 20 Jun 09
Posts: 351
ID: 42198
Credit: 11,898,570
RAC: 0
321 LLR Gold: Earned 500,000 credits (547,769)Cullen LLR Silver: Earned 100,000 credits (158,867)PPS LLR Silver: Earned 100,000 credits (162,534)PSP LLR Silver: Earned 100,000 credits (134,373)SoB LLR Gold: Earned 500,000 credits (510,012)SR5 LLR Silver: Earned 100,000 credits (266,757)SGS LLR Gold: Earned 500,000 credits (510,560)TRP LLR Silver: Earned 100,000 credits (242,439)Woodall LLR Gold: Earned 500,000 credits (508,989)321 Sieve Silver: Earned 100,000 credits (200,123)Cullen/Woodall Sieve (suspended) Silver: Earned 100,000 credits (229,801)PPS Sieve Ruby: Earned 2,000,000 credits (4,317,221)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Bronze: Earned 10,000 credits (21,147)TRP Sieve (suspended) Silver: Earned 100,000 credits (333,494)AP 26/27 Bronze: Earned 10,000 credits (24,117)GFN Ruby: Earned 2,000,000 credits (3,730,320)
Message 38231 - Posted: 12 Jul 2011 | 10:32:34 UTC

It is already in wiki --- I wrote it months ago!!

What may be needed is a link to the wiki on the home page or the side bar.

I would suggest either in "Community" or "Other".

Perhaps a basic primer on what Prime Number, Composite Number and a Factor actually mean would help to reduce this perrenial misunderstanding.

I remember one student at uni arguing strongly that 5 is not prime, [10, 0.5] are its factors!! I was never sure he understood where he was wrong.
____________
Member team AUSTRALIA
My lucky number is 9291*2^1085585+1

Profile DaveBProject donor
Avatar
Send message
Joined: 20 Jun 09
Posts: 351
ID: 42198
Credit: 11,898,570
RAC: 0
321 LLR Gold: Earned 500,000 credits (547,769)Cullen LLR Silver: Earned 100,000 credits (158,867)PPS LLR Silver: Earned 100,000 credits (162,534)PSP LLR Silver: Earned 100,000 credits (134,373)SoB LLR Gold: Earned 500,000 credits (510,012)SR5 LLR Silver: Earned 100,000 credits (266,757)SGS LLR Gold: Earned 500,000 credits (510,560)TRP LLR Silver: Earned 100,000 credits (242,439)Woodall LLR Gold: Earned 500,000 credits (508,989)321 Sieve Silver: Earned 100,000 credits (200,123)Cullen/Woodall Sieve (suspended) Silver: Earned 100,000 credits (229,801)PPS Sieve Ruby: Earned 2,000,000 credits (4,317,221)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Bronze: Earned 10,000 credits (21,147)TRP Sieve (suspended) Silver: Earned 100,000 credits (333,494)AP 26/27 Bronze: Earned 10,000 credits (24,117)GFN Ruby: Earned 2,000,000 credits (3,730,320)
Message 38234 - Posted: 12 Jul 2011 | 12:52:22 UTC - in response to Message 38231.

I have just checked and the page I wrote is now missing, as is the page index. In short the PG wiki is now a mess!!

There are a few pages that explain details of the methods used for sieving in PG but they are for those who already understand the basic theory, notations and nomecular. They are not like the basic introductions I wrote.

The PG wiki home page is http://primegrid.wikia.com/wiki/PrimeGrid_Wiki .

My page read :-

ABOUT SIEVING

Sieves can be catagorised as being either absolute or partial. An absolute sieve results in a list of numbers that are all prime. A partial sieve results in a list of numbers that include all the primes in the search field and may also contain some composite numbers, however many composite numbers have been eliminated by the process.

Prime grid uses only partial sieves for the reasons explained below.

There are several types of sieve - the Erastophenes Sieve, the Polemaic Sieve, the Factoral Sieve and the Fermat Primality Test. Most of these have other derived test methods which are either more accurate or faster, or both.

The Erastophenes Sieve is a manual method which works by writing the numbers to be tested in a grid :-


1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64

1 is not considered a prime, so beginning with 2 set each second number to 0 as not being a prime :-


1 2 3 0 5 0 7 0
9 0 11 0 13 0 15 0
17 0 19 0 21 0 23 0
25 0 27 0 29 0 31 0
33 0 35 0 37 0 39 0
41 0 43 0 45 0 47 0
49 0 51 0 53 0 55 0
57 0 59 0 61 0 63 0

Go to the next non zero number (3) and set each third number to 0, repeat this step until no further numbers are set to zero :-


1 2 3 0 5 0 7 0
0 0 11 0 13 0 0 0
17 0 19 0 0 0 23 0
0 0 0 0 29 0 31 0
0 0 0 0 37 0 0 0
41 0 43 0 0 0 47 0
0 0 0 0 53 0 0 0
0 0 59 0 61 0 0 0

This leaves the prime numbers as 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61.

The Polemaic Sieve (originally deduced by Potlemys School of mathematics) is an arithmatic based method developed by others into more precise forms of partial sieves.

This method uses the fact that any number (x) can be written as a multiple of 6 plus one of -1, 0, 1, 2, 3, 4, or as an equation

x = 6n+{-1,0,1,2,3,4}

As 6n must be even then 6n+{0,2,4} must also be even and not prime, similarly 6n+{0,3} must be divisible by 3 and hence not prime. This removes 2/3 of the possible candidates for primality from any list of consecutive numbers. In practice the number being tested is divided by 6n and the remainder examined with only those having a remainder of -1 or 1 being possible primes.

As a collary to this the number between any pair of dual (twin) primes must be a multiple of 6.

The Sieve of Atkins is similar except it uses 60n and remainders that are multiples of 2, 3 or 5 can be eliminated. Further procedures of a complexity beyond this atricle can be carried out to prove primality, these are described at http://wikipedia.atpedia.com/en/articles/s/i/e/Sieve_of_Atkin_95b8.html .

The Factoral Sieve is an arithmetic variation of the Sieve of Erastophenes. It can be applied to any number and can be either absolute or partial. The candidate number is tested by division by all the prime numbers less than the square root of the candidate number. If any test gives no remainder then the number is composite and no further testing is required.

To be an absolute sieve the test uses a table of prime numbers which must be complete to the square root of the candidate number, testing beyond this is not required since at least one factor of any composite number must be less than the square root of that number. Only prime numbers need to be used as any factor of a composite number which is itself composite can be further factorised until only prime factors remain.

If testing is carried out to less than the square root of the candidate number then the result will be to find if it is composite or a possible prime number, i.e. it becomes a partial sieve. This test is one of the main ones used by prime grid but with the very large numbers being used it is not practical to test to the square root as the list of square roots would be far too big, taking several days to download and taking up many times the currenty hard drive capacity. The testing process for numbers with over 10E6 digits would take even the fastest of modern computers several years to complete one test. Sieving with only the first few hundred prime numbers will however greatly reduce the requirements of more advanced LLR testing used to prove, in an absolute form, the primality of a number.

Fermats Primality Test is a partial test that has been developed into an absolute test by several mathematicians. It is based on Fermats Little Therom which states that if any number less than the candidate number is raised to the power of the candidate number minus 1 then it will not be equal to 1 (mod candidate number) if it is composite.

If it is equal to 1(mod candidate number) then it may be prime.

Mathematically if the randomly chosen number is "a" and 1<a<c where c is the candidate number then it is not prime if a^(c-1) /= 1 (mod c). If all possible values of "a" yeild a possible prime then either c is prime or a Carmichael number.

____________
Member team AUSTRALIA
My lucky number is 9291*2^1085585+1

Brook HarsteProject donor
Avatar
Send message
Joined: 30 Nov 08
Posts: 1345
ID: 32401
Credit: 805,483,198
RAC: 0
Discovered 2 mega primesFound 1 prime in the 2019 Tour de Primes321 LLR Jade: Earned 10,000,000 credits (10,334,077)Cullen LLR Turquoise: Earned 5,000,000 credits (5,010,955)ESP LLR Turquoise: Earned 5,000,000 credits (7,439,418)Generalized Cullen/Woodall LLR Turquoise: Earned 5,000,000 credits (5,501,906)PPS LLR Sapphire: Earned 20,000,000 credits (26,697,006)PSP LLR Turquoise: Earned 5,000,000 credits (6,184,417)SoB LLR Jade: Earned 10,000,000 credits (12,120,365)SR5 LLR Turquoise: Earned 5,000,000 credits (9,234,440)SGS LLR Turquoise: Earned 5,000,000 credits (5,201,403)TRP LLR Turquoise: Earned 5,000,000 credits (5,628,223)Woodall LLR Turquoise: Earned 5,000,000 credits (5,061,985)321 Sieve Amethyst: Earned 1,000,000 credits (1,027,534)Cullen/Woodall Sieve (suspended) Jade: Earned 10,000,000 credits (17,370,919)Generalized Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,014,372)PPS Sieve Double Bronze: Earned 100,000,000 credits (129,430,775)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,083,315)TRP Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,629,248)AP 26/27 Emerald: Earned 50,000,000 credits (56,876,924)GFN Double Silver: Earned 200,000,000 credits (286,079,854)PSA Double Silver: Earned 200,000,000 credits (200,556,062)
Message 38239 - Posted: 12 Jul 2011 | 15:28:53 UTC - in response to Message 38234.

I think just a few qualified people should be allowed to edit the wiki such as yourself DaveB.
Also I don't think the wiki should ever point back to the forums for explanations. It should stay on the wiki. <JMHO>
____________

Profile WarpedProject donor
Avatar
Send message
Joined: 25 Aug 08
Posts: 288
ID: 27792
Credit: 28,151,335
RAC: 1
321 LLR Silver: Earned 100,000 credits (105,595)Cullen LLR Silver: Earned 100,000 credits (100,566)PPS LLR Silver: Earned 100,000 credits (467,197)PSP LLR Silver: Earned 100,000 credits (117,635)SoB LLR Bronze: Earned 10,000 credits (70,753)SR5 LLR Bronze: Earned 10,000 credits (44,970)SGS LLR Silver: Earned 100,000 credits (346,635)TRP LLR Silver: Earned 100,000 credits (298,952)Woodall LLR Silver: Earned 100,000 credits (107,939)321 Sieve Gold: Earned 500,000 credits (591,806)Cullen/Woodall Sieve (suspended) Bronze: Earned 10,000 credits (93,149)Generalized Cullen/Woodall Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,013,621)PPS Sieve Jade: Earned 10,000,000 credits (17,468,069)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,203,660)TRP Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,431,176)AP 26/27 Bronze: Earned 10,000 credits (27,387)GFN Silver: Earned 100,000 credits (124,947)PSA Ruby: Earned 2,000,000 credits (4,529,162)
Message 38240 - Posted: 12 Jul 2011 | 17:30:10 UTC

This thread is similar to the discussion we had in the "General Discussion" Forum.

____________
Warped

DirkProject donor
Send message
Joined: 10 Mar 10
Posts: 512
ID: 56675
Credit: 721,874,192
RAC: 0
Discovered 1 mega primeDiscovered 1 Fermat divisor321 LLR Turquoise: Earned 5,000,000 credits (5,424,768)Cullen LLR Turquoise: Earned 5,000,000 credits (5,256,909)ESP LLR Turquoise: Earned 5,000,000 credits (5,021,690)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (4,610,120)PPS LLR Turquoise: Earned 5,000,000 credits (5,082,604)PSP LLR Turquoise: Earned 5,000,000 credits (5,114,046)SoB LLR Turquoise: Earned 5,000,000 credits (5,542,658)SR5 LLR Turquoise: Earned 5,000,000 credits (5,011,433)SGS LLR Turquoise: Earned 5,000,000 credits (5,035,343)TRP LLR Turquoise: Earned 5,000,000 credits (5,149,540)Woodall LLR Turquoise: Earned 5,000,000 credits (5,222,602)321 Sieve Turquoise: Earned 5,000,000 credits (5,032,392)Cullen/Woodall Sieve (suspended) Silver: Earned 100,000 credits (201,767)Generalized Cullen/Woodall Sieve (suspended) Jade: Earned 10,000,000 credits (10,158,539)PPS Sieve Double Silver: Earned 200,000,000 credits (284,228,796)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Jade: Earned 10,000,000 credits (12,293,182)TRP Sieve (suspended) Jade: Earned 10,000,000 credits (10,183,808)AP 26/27 Emerald: Earned 50,000,000 credits (59,684,182)GFN Emerald: Earned 50,000,000 credits (83,615,774)PSA Double Silver: Earned 200,000,000 credits (200,004,037)
Message 38267 - Posted: 13 Jul 2011 | 20:23:36 UTC

So, the process of finding large primes is broken into two steps. Step 1 is to run a sieve against a set of large candidate numbers. The sieve checks to see whether (comparatively) small primes are factors of any of the candidates. This rapidly eliminates a large number of the candidates in less time than it would take to test them with LLR.


So I come to a technical question: What are "(comparatively) small primes" that are used to sieve, in other words to check if they are factors of any of the candidates? Are we talking about the first few hundred primes, the first few thousand primes, or some other series of primes?

Iain BethuneProject donor
Honorary cruncher
Send message
Joined: 28 Jan 09
Posts: 1588
ID: 34775
Credit: 194,056,043
RAC: 0
321 LLR Gold: Earned 500,000 credits (597,175)Cullen LLR Amethyst: Earned 1,000,000 credits (1,355,381)ESP LLR Turquoise: Earned 5,000,000 credits (5,048,594)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,564,412)PPS LLR Amethyst: Earned 1,000,000 credits (1,025,115)PSP LLR Sapphire: Earned 20,000,000 credits (28,367,849)SoB LLR Jade: Earned 10,000,000 credits (16,215,329)SR5 LLR Turquoise: Earned 5,000,000 credits (5,189,992)SGS LLR Amethyst: Earned 1,000,000 credits (1,244,067)TRP LLR Turquoise: Earned 5,000,000 credits (5,169,405)Woodall LLR Amethyst: Earned 1,000,000 credits (1,070,956)321 Sieve Bronze: Earned 10,000 credits (20,003)Cullen/Woodall Sieve (suspended) Silver: Earned 100,000 credits (200,371)Generalized Cullen/Woodall Sieve (suspended) Jade: Earned 10,000,000 credits (11,645,025)PPS Sieve Turquoise: Earned 5,000,000 credits (7,536,532)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,017,144)TRP Sieve (suspended) Gold: Earned 500,000 credits (554,946)AP 26/27 Ruby: Earned 2,000,000 credits (3,577,848)GFN Emerald: Earned 50,000,000 credits (97,047,976)PSA Ruby: Earned 2,000,000 credits (4,606,694)
Message 38277 - Posted: 14 Jul 2011 | 8:52:02 UTC - in response to Message 38267.
Last modified: 14 Jul 2011 | 8:52:51 UTC

The largest (small) prime which has been checked against the candidates is known as the depth of the sieve. In the case of the PPS Seive (according to this post http://www.primegrid.com/forum_thread.php?id=3467&nowrap=true#37798) the current sieve depth is ~650T for the range 3M-6M.

What this means is that for all the ks we are testing in PPS, for values of n in the range 3M-6M, we have tested all primes up to 650x10^12 (650 million million) to see if they are factors of the Proth & Riesel Primes (k*2^n+/-1) given by the k & N limits above.

So the small primes we are using for the sieve are actually quite large (up to around 10^14), although the candidate numbers we are testing are much much larger (2^6M ~= 10^2M).

In any given Sieve WU on PrimeGrid, you will be assigned a range of small primes (typically 50x10^9) at a time, to test against a range of k's at a given N.

Hope that answers the question (and I haven't made any silly mistakes).
____________
Twitter: IainBethune
Proud member of team "Aggie The Pew". Go Aggie!
3073428256125*2^1290000-1 is Prime!

DirkProject donor
Send message
Joined: 10 Mar 10
Posts: 512
ID: 56675
Credit: 721,874,192
RAC: 0
Discovered 1 mega primeDiscovered 1 Fermat divisor321 LLR Turquoise: Earned 5,000,000 credits (5,424,768)Cullen LLR Turquoise: Earned 5,000,000 credits (5,256,909)ESP LLR Turquoise: Earned 5,000,000 credits (5,021,690)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (4,610,120)PPS LLR Turquoise: Earned 5,000,000 credits (5,082,604)PSP LLR Turquoise: Earned 5,000,000 credits (5,114,046)SoB LLR Turquoise: Earned 5,000,000 credits (5,542,658)SR5 LLR Turquoise: Earned 5,000,000 credits (5,011,433)SGS LLR Turquoise: Earned 5,000,000 credits (5,035,343)TRP LLR Turquoise: Earned 5,000,000 credits (5,149,540)Woodall LLR Turquoise: Earned 5,000,000 credits (5,222,602)321 Sieve Turquoise: Earned 5,000,000 credits (5,032,392)Cullen/Woodall Sieve (suspended) Silver: Earned 100,000 credits (201,767)Generalized Cullen/Woodall Sieve (suspended) Jade: Earned 10,000,000 credits (10,158,539)PPS Sieve Double Silver: Earned 200,000,000 credits (284,228,796)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Jade: Earned 10,000,000 credits (12,293,182)TRP Sieve (suspended) Jade: Earned 10,000,000 credits (10,183,808)AP 26/27 Emerald: Earned 50,000,000 credits (59,684,182)GFN Emerald: Earned 50,000,000 credits (83,615,774)PSA Double Silver: Earned 200,000,000 credits (200,004,037)
Message 38293 - Posted: 14 Jul 2011 | 17:17:14 UTC - in response to Message 38277.

A very clear and understandable explanation, even for a non-mathematician like me. Thanks a lot!

Profile Rick Reynolds
Avatar
Send message
Joined: 13 Aug 10
Posts: 7880
ID: 65483
Credit: 5,312,080,766
RAC: 66,236
Discovered 2 mega primesFound 2 primes in the 2018 Tour de PrimesFound 2 primes in the 2019 Tour de PrimesFound 12 primes in the 2020 Tour de Primes321 LLR Jade: Earned 10,000,000 credits (10,244,909)Cullen LLR Jade: Earned 10,000,000 credits (10,194,451)ESP LLR Turquoise: Earned 5,000,000 credits (5,174,327)Generalized Cullen/Woodall LLR Turquoise: Earned 5,000,000 credits (5,028,260)PPS LLR Emerald: Earned 50,000,000 credits (61,072,468)PSP LLR Turquoise: Earned 5,000,000 credits (5,151,448)SoB LLR Turquoise: Earned 5,000,000 credits (5,014,268)SR5 LLR Jade: Earned 10,000,000 credits (14,871,275)SGS LLR Turquoise: Earned 5,000,000 credits (7,860,522)TRP LLR Jade: Earned 10,000,000 credits (11,130,742)Woodall LLR Turquoise: Earned 5,000,000 credits (5,419,909)321 Sieve Double Bronze: Earned 100,000,000 credits (101,538,236)Cullen/Woodall Sieve (suspended) Double Bronze: Earned 100,000,000 credits (127,922,665)Generalized Cullen/Woodall Sieve (suspended) Sapphire: Earned 20,000,000 credits (30,984,158)PPS Sieve Double Ruby: Earned 2,000,000,000 credits (2,840,173,136)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Turquoise: Earned 5,000,000 credits (8,134,964)TRP Sieve (suspended) Turquoise: Earned 5,000,000 credits (7,013,696)AP 26/27 Double Silver: Earned 200,000,000 credits (276,723,135)GFN Double Silver: Earned 200,000,000 credits (323,467,712)PSA Double Amethyst: Earned 1,000,000,000 credits (1,370,700,486)
Message 38294 - Posted: 14 Jul 2011 | 17:33:10 UTC

One reason we at Aggie The Pew feel lucky to have him on our team :)
____________
@AggieThePew

Iain BethuneProject donor
Honorary cruncher
Send message
Joined: 28 Jan 09
Posts: 1588
ID: 34775
Credit: 194,056,043
RAC: 0
321 LLR Gold: Earned 500,000 credits (597,175)Cullen LLR Amethyst: Earned 1,000,000 credits (1,355,381)ESP LLR Turquoise: Earned 5,000,000 credits (5,048,594)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,564,412)PPS LLR Amethyst: Earned 1,000,000 credits (1,025,115)PSP LLR Sapphire: Earned 20,000,000 credits (28,367,849)SoB LLR Jade: Earned 10,000,000 credits (16,215,329)SR5 LLR Turquoise: Earned 5,000,000 credits (5,189,992)SGS LLR Amethyst: Earned 1,000,000 credits (1,244,067)TRP LLR Turquoise: Earned 5,000,000 credits (5,169,405)Woodall LLR Amethyst: Earned 1,000,000 credits (1,070,956)321 Sieve Bronze: Earned 10,000 credits (20,003)Cullen/Woodall Sieve (suspended) Silver: Earned 100,000 credits (200,371)Generalized Cullen/Woodall Sieve (suspended) Jade: Earned 10,000,000 credits (11,645,025)PPS Sieve Turquoise: Earned 5,000,000 credits (7,536,532)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,017,144)TRP Sieve (suspended) Gold: Earned 500,000 credits (554,946)AP 26/27 Ruby: Earned 2,000,000 credits (3,577,848)GFN Emerald: Earned 50,000,000 credits (97,047,976)PSA Ruby: Earned 2,000,000 credits (4,606,694)
Message 38299 - Posted: 14 Jul 2011 | 18:36:56 UTC - in response to Message 38294.

One reason we at Aggie The Pew feel lucky to have him on our team :)


Join us! We can't guarantee you'll learn any maths but we can guarantee you'll have plenty of fun!

____________
Twitter: IainBethune
Proud member of team "Aggie The Pew". Go Aggie!
3073428256125*2^1290000-1 is Prime!

Message boards : Number crunching : Prime number search

[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2021 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 0.00, 0.04, 0.05
Generated 25 Oct 2021 | 19:46:32 UTC