Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummerslowrise

Message boards :
Number crunching :
Prime number search
Author 
Message 

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  


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


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_g6Volunteer developer
Send message
Joined: 4 Jul 06 Posts: 915 ID: 3110 Credit: 183,164,814 RAC: 4,009

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


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  


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


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
 


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^12900001 is Prime!  


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
 

Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13513 ID: 53948 Credit: 236,922,854 RAC: 3,199

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 rereport 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 75898^{524288}+1  


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 rereport 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
 


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^12900001 is Prime!  


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
 

Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13513 ID: 53948 Credit: 236,922,854 RAC: 3,199

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 75898^{524288}+1  

Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13513 ID: 53948 Credit: 236,922,854 RAC: 3,199

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 75898^{524288}+1  


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

Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13513 ID: 53948 Credit: 236,922,854 RAC: 3,199

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 75898^{524288}+1  


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>
____________
 


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  


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^(c1) /= 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  


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>
____________
 


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


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?
 


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 3M6M.
What this means is that for all the ks we are testing in PPS, for values of n in the range 3M6M, 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^12900001 is Prime!  


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


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


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^12900001 is Prime!  

Message boards :
Number crunching :
Prime number search 