Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummers-lowrise
|
Message boards :
Seventeen or Bust :
Difference between SoB and PSP WUs?
| Author |
Message |
|---|
|
|
|
It's my understanding that SoB and PSP are, when all is said and done, subsets of essentially the same problem, with some overlap in the numbers that need to be tested for primality.
So why are the WUs of such dramatically different magnitude of size. Are the two projects working on different ends of the same problem, such that PSP will eventually have to deal with much longer WUs and SoB might have to deal with shorter ones, or do they simply take very different approaches to how they split up the work?
As I'm working my way towards SoB Silver, I'm kind of curious about the mechanics of the difference between the two projects...
-JMP | |
|
|
|
|
Quick answer that might be sufficient. . . let me know if you need more details.
Both projects are working on numbers of the form k*2^n+1, but they're working with different k values. Seventeen or bust has been working on their k values longer than PSP has been working on theirs, so while the current PSP n values are in the n=8,000,000 range (for first pass, current work units being handed out are double check and in the n=5,000,000 range), SoB work units have a n value in the n=17,000,000 range. Much bigger numbers means MUCH longer run times.
If PSP doesn't find any primes in the next few years, they'll probably be in the 17,000,000 range, while SoB might be in the 27,000,000 range. In other words, length of work units is only going up. | |
|
|
|
|
Right, but there are multiple k values to be tested, and a few of the k values (and by extension every n value paired with that k value) are on the to do list for both SoB and PSP. Are the projects working through ranges of n, testing them for all of the possible k values, or are they working through the values of n for a single k, then moving on to another k?
I assume that PSP isn't retesting n values for the k values included in SoB that have already been tested. The question then becomes one of how they're each working their way through the tests and how they coordinate on the overlapping range...
-JMP | |
|
Scott Brown Volunteer moderator
Project administrator
Volunteer tester
Project scientist
Send message
Joined: 17 Oct 05
Posts: 2392
ID: 1178
Credit: 18,650,932,838
RAC: 6,986,493
                                                
|
|
Quoted from John Blazek's post:
"About the Sierpinski Problem
Wacław Franciszek Sierpiński (14 March 1882 — 21 October 1969), a Polish mathematician, was known for outstanding contributions to set theory, number theory, theory of functions and topology. It is in number theory where we find the Sierpinski problem.
Basically, the Sierpinski problem is "What is the smallest Sierpinski number"
First we look at Proth numbers (named after the French mathematician François Proth). A Proth number is a number of the form k*2^n+1 where k is odd, n is a positive integer, and 2^n>k.
A Sierpinski number is an odd k such that the Proth number k*2^n+1 is not prime for all n. For example, 3 is not a Sierpinski number because n=2 produces a prime number (3*2^2+1=13). In 1962, John Selfridge proved that 78,557 is a Sierpinski number...meaning he showed that for all n, 78557*2^n+1 was not prime.
Most number theorists believe that 78,557 is the smallest Sierpinski number, but it hasn't yet been proven. In order to prove it, it has to be shown that every single k less than 78,557 is not a Sierpinski number, and to do that, some n must be found that makes k*2^n+1 prime.
The smallest proven 'prime' Sierpinski number is 271,129. In order to prove it, it has to be shown that every single 'prime' k less than 271,129 is not a Sierpinski number, and to do that, some n must be found that makes k*2^n+1 prime.
Seventeen or Bust is working on the Sierpinski problem and the Prime Sierpinski Project is working on the 'prime' Sierpinski problem.
.
.
.
Fortunately, the two projects combined their sieving efforts into a single file. Therefore, PrimeGrid's PSP/SoB sieve supports both projects."
See John's full post here.
____________
141941*2^4299438-1 is prime!
 | |
|
|
|
Right, but there are multiple k values to be tested, and a few of the k values (and by extension every n value paired with that k value) are on the to do list for both SoB and PSP. Are the projects working through ranges of n, testing them for all of the possible k values, or are they working through the values of n for a single k, then moving on to another k?
I assume that PSP isn't retesting n values for the k values included in SoB that have already been tested. The question then becomes one of how they're each working their way through the tests and how they coordinate on the overlapping range...
-JMP
The numbers that overlap are being tested by SoB only.
Both projects are working all their assigned k values simultaneously with increasing n values.
Hope this helps | |
|
|
|
Right, but there are multiple k values to be tested, and a few of the k values (and by extension every n value paired with that k value) are on the to do list for both SoB and PSP. Are the projects working through ranges of n, testing them for all of the possible k values, or are they working through the values of n for a single k, then moving on to another k?
I assume that PSP isn't retesting n values for the k values included in SoB that have already been tested. The question then becomes one of how they're each working their way through the tests and how they coordinate on the overlapping range...
-JMP
The numbers that overlap are being tested by SoB only.
Both projects are working all their assigned k values simultaneously with increasing n values.
Hope this helps
That helps quite a bit. So SoB is now up to higher n values across all of its k values, while PSP is at a lower n value for all of its k values other than the ones that are also part of SoB's list of k values.
My next question is that given that the definition of a Sierpinski number requires that k*2^n+1 is not prime for all values of n, will testing go on indefinitely as n rises, or is there some point at which there can be a proof that if none of the n values up to that point yield a prime, none beyond that will? In theory, without such a proof, there is no way to demonstrate that k*2^n+1 is not prime for all values of n, only ways to disprove it by finding a prime...
-JMP | |
|
|
|
|
Current known sierpinski numbers have what's called a covering set. It's basically a set of factors, where it can be shown that for every n value, k*2^n+1 is divisible by one of the factors. (eg. if n = 0 mod 2 k2^n+1 is divisible by 3, if n=0 mod 3 k2^n+1 is divisible by 7. . . . all the way up to some number that completes a loop such that dividing any n by that number will fall into one of the categories.) There's more info somewhere on the web, can't remember where I read about all of it.
For the numbers that PSP and SoB are working on it can be (and has been) proved that they do NOT have a covering set. Without a covering set there is no known way to show that a number IS a sierpinski number, so we're left with trying to prove that each of these is not. Our only method to do that is to find an n which makes k*2^n+1 prime.
So to quickly answer your question, there is no end in sight, and we'll keep looking until we find a prime for each of the candidates, or we'll get tired of trying. | |
|
|
|
|
If no prime is found for a particular k, then searching will go on forever. (Hence the meaning of "or Bust" in the title.) Most people agree that there will eventually be a prime found for all k's lower than 78557 because every known Sierpinski number has a small covering set, whereas the k's being tested by SoB do not have small covering sets (or any covering set, otherwise that number would be the conjectured answer to the Sierpinski problem, and not 78557).
A good page on Sierpinski numbers and their covering sets: http://primes.utm.edu/glossary/page.php?sort=SierpinskiNumber | |
|
|
|
|
It is not quite true that every proven Sierpiński number has a covering set.
You can create a k such that some exponents n are covered by an algebraic factorization, and only the remaining exponents are accounted for by a small set of primes.
In the following example, I follow this source:
Anatoly S. Izotov, A Note on Sierpinski Numbers, Fibonacci Quarterly A 33.3(1995), 206.
Let k=166528519813771386496141126495646000631459761803173801006187890625.
When the exponent n is of the form n = 4m+2, we have the Aurifeuillean factorization:
166528519813771386496141126495646000631459761803173801006187890625 * 2^(4m + 2) + 1
= (408079060739180032846765042950625 * 2^(2m + 1) + 20200966826842225 * 2^(m + 1) + 1)*(408079060739180032846765042950625 * 2^(2m + 1) - 20200966826842225 * 2^(m + 1) + 1)
When n is not on this form (i.e. when n is 0 or ±1 modulo 4), 166528519813771386496141126495646000631459761803173801006187890625 * 2^n + 1 is divisible by one of the primes {3, 17, 257, 641, 65537, 6700417}.
Together, the Aurifeuille thing and the prime set (consisting of the prime factors of Fermat numbers F0, F2, F3, F4, and F5, in case you did not notice) prove that we have a Sierpiński number. But it is not expected that there exists a finite covering set for this k. The numbers k*2^(4m+2)+1 probably require an infinite set to cover?
/JeppeSN | |
|
|
|
|
I searched and researched a bit more and found a smaller example (with another prime set than in Izotov's example).
So I repeat my previous post with smaller numbers:
Let k=4008735125781478102999926000625.
When the exponent n is of the form n = 4m+2, we have the Aurifeuillean factorization:
4008735125781478102999926000625 * 2^(4m + 2) + 1
= (2002182590520025 * 2^(2m + 1) + 44745755 * 2^(m + 1) + 1)*(2002182590520025 * 2^(2m + 1) - 44745755 * 2^(m + 1) + 1)
When n is not on this form (i.e. when n is 0 or ±1 modulo 4), 4008735125781478102999926000625 * 2^n + 1 is divisible by one of the primes {3, 17, 97, 241, 257, 673}.
Together, the Aurifeuille thing and the prime set prove that we have a Sierpiński number. But it is not expected that there exists a finite covering set for this k. The numbers k*2^(4m+2)+1 probably require an infinite set to cover?
/JeppeSN
| |
|
 Michael GoetzVolunteer moderator
Project administrator
Send message
Joined: 21 Jan 10
Posts: 14011
ID: 53948
Credit: 433,165,326
RAC: 1,015,136
                              
|
Right, but there are multiple k values to be tested, and a few of the k values (and by extension every n value paired with that k value) are on the to do list for both SoB and PSP. Are the projects working through ranges of n, testing them for all of the possible k values, or are they working through the values of n for a single k, then moving on to another k?
I assume that PSP isn't retesting n values for the k values included in SoB that have already been tested. The question then becomes one of how they're each working their way through the tests and how they coordinate on the overlapping range...
-JMP
Sob has 5 k's remaining. (Two of these k's are prime and 3 are composite.)
PSP has 9 k's remaining. Two of those 9 k's (22699 and 67607) are the two prime k's already being searched by SoB. It would be wasteful to search the same numbers twice, so PSP isn't searching those two. PSP is therefore searching 7 k's.
In each project, we're searching all k's simultaneously while increasing n. It IS possible to conduct the search in a different order. We could do it one k at a time if we wanted.
SoB is much further along than PSP for a variety of reasons. The leading edge of PSP is around n=19.8M while the leading edge of SoB is around n=31.6M. We're in the middle of double checking old SoB work, however, so we're not currently testing n=31.6M numbers for SoB. The SoB double check is currently around n=24.9M. Current tasks for PSP therefore have an n around 19.8 million while SoB's tasks are at n=24.9 million. That's why the SoB tasks are larger.
____________
My lucky number is 75898524288+1 | |
|
Michael GoetzVolunteer moderator
Project administrator
Send message
Joined: 21 Jan 10
Posts: 14011
ID: 53948
Credit: 433,165,326
RAC: 1,015,136
|
My next question is that given that the definition of a Sierpinski number requires that k*2^n+1 is not prime for all values of n, will testing go on indefinitely as n rises ... ?
So to quickly answer your question, there is no end in sight, and we'll keep looking until we find a prime for each of the candidates, or we'll get tired of trying.
This is literally a case where we're either going to find primes for the remaining k's or die trying. It's entirely possible that these two conjectures will outlive all of us.
If the conjectures are false, i.e., one of the remaining k's is indeed a Sierpinski number for which there is no prime at any n, there is no known way of determining that. This project is only capable of proving the conjectures are correct by finding the needed primes. There's no known way of disproving the conjecture. If the conjectures are false, the search will go on forever.
Of course, we're doing this because it's believed that the conjectures are correct.
____________
My lucky number is 75898524288+1 | |
|
Message boards :
Seventeen or Bust :
Difference between SoB and PSP WUs? |
