Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummers-lowrise
|
Message boards :
Seventeen or Bust :
Are people even sure 78557 is the smallest k?
| Author |
Message |
|---|
 Bur Volunteer tester
Send message
Joined: 25 Feb 20
Posts: 515
ID: 1241833
Credit: 414,481,880
RAC: 219
                
|
|
Seeing how SoB has gone to really large n values, are mathematicians rather certain that 78557 is the smallest Sierpinski number? I know there is no proof, but it appears to me, that some conjectures are thought to be true (like Riemann zeta) because there are lots of hints they are true.
Are there some arguments pro 78557 being the smallest Sierpinski number? If so, are there some ideas about the magnitude of n for the remaining k's?
Is there a point when such a large n is reached that doubt will be cast upon 78557 actually being the smallest Sierpinski number?
Is anything known about why some k < 78557 require such large n-values before resulting in a prime while the majority doesn't? | |
|
Ravi FernandoProject administrator
Volunteer tester
Project scientist
Send message
Joined: 21 Mar 19
Posts: 211
ID: 1108183
Credit: 13,824,824
RAC: 7,626
              
|
Is anything known about why some k < 78557 require such large n-values before resulting in a prime while the majority doesn't?
Yes. Some k's produce lots of candidates that are divisible by small primes, and some don't. The "weight" of a k is a relative measure of how many candidates survive the sieving process (i.e. aren't divisible by any small primes). High-weight k's produce many candidates (and are expected to produce many primes), and low-weight k's produce few candidates (and are expected to produce few primes). Known Sierpinski numbers like 78557 have weight 0, because every candidate is divisible by a small prime. (Some other known Sierpinski numbers use algebraic factorizations along with small primes to rule out the existence of a prime. Really the definition of "weight" should incorporate these algebraic factorizations too. But in any case none of the SoB k's has any algebraic factorizations.)
Seeing how SoB has gone to really large n values, are mathematicians rather certain that 78557 is the smallest Sierpinski number? I know there is no proof, but it appears to me, that some conjectures are thought to be true (like Riemann zeta) because there are lots of hints they are true.
Are there some arguments pro 78557 being the smallest Sierpinski number? If so, are there some ideas about the magnitude of n for the remaining k's?
Yves Gallot has made a calculator (link) that estimates the weight of any given k. (Try k = 3, 5, 55459, 67607, 78557, etc.) Using the weights of the SoB k's, you can predict how long they should take to produce a prime. Yves made some predictions in this 2001 paper, which have been remarkably accurate so far. I think this is the strongest evidence we have in favor of the conjecture being true: the weight of a multiplier k, after adjusting for algebraic factorizations, is empirically a good predictor of how frequently that k produces primes. So every k whose weight isn't literally 0 should eventually produce a prime.
The bad news: the conjecture is not likely to be proved any time soon. Given where we are right now, there is about a 93.5% chance that proving the conjecture will require finding a prime with over a billion digits; a 54% chance of over a trillion digits, 28% over 10^15 digits, 14% over 10^18 digits, etc. (Primes become less and less common as n grows, so asymptotically we expect a given k to produce about X primes below n = 2^(X/weight). Remember that n is itself an exponent, and all of these k's have very small weights.) So it's an uphill fight, to say the least.
Is there a point when such a large n is reached that doubt will be cast upon 78557 actually being the smallest Sierpinski number?
For each of the individual SoB k's, it's pretty surprising that they haven't produced a prime so far. (Very roughly, the five k's had 98%, 80%, 98.5%, 99.6%, and 76% chances respectively of producing primes below the current leading edge.) But there are a lot of odd numbers 1 < k < 78557, so it's not surprising that five of them have been "unlucky".
Maybe a more useful way to look at your question: given what we know now, and assuming that primes of the form k*2^n + 1 work how we expect them to, for what value of n would it be shocking if we haven't finished SoB by n? Let's say "shocking" means "<1% chance". Then the answer to the question is about n = 6 * 10^29, which corresponds to primes with 200 billion billion billion digits. If we get to that point and still haven't finished SoB, then it may be worthwhile for Skynet to take a break from number crunching and look for a theoretical reason it's not finding any primes. | |
|
|
|
Given where we are right now, there is about a 93.5% chance that proving the conjecture will require finding a prime with over a billion digits; a 54% chance of over a trillion digits, 28% over 10^15 digits, 14% over 10^18 digits, etc.
So obviously the last few numbers in that list are pretty unfathomable, but megaprimes have gone from something that made the news to something we're discovering multiple of every week in a pretty short fashion. If we (falsely?) assume that hardware improvements don't slow down, are there any really significant hurdles on the march to gigaprimes in our lifetimes? It seems to me like GIMPS will get there, but does SoB scale effectively for that to be feasible? | |
|
|
|
|
It was kind of hinted at in one of the previous replies, but I think it's worth pointing out (and it's probably covered better than I can in one of the links). The reason we know 78557 is a Sierpinski number is that it has been shown to have a so called "Covering Set"; a set of small primes that it can be shown with modular arithmetic to evenly divide k*2^n+1 for every n. (I think there are 19 of the primes, and it can be shown that if n/18 has remainder zero, this prime divides, 78557*2^n+1, and if n/18 has remainder 1, this other prime divides 78557*2^n+1, and so on for all 19 possible remainders of n/18)
All known Sierpinski numbers have a fairly small covering set.
All the ks remaining in SoB have been proven to NOT have a covering set of any size.
So the fact that we know they don't have a covering set gives us a little bit of hope that there will eventually be a prime for each of the remaining k.
This is all from memory of reading up on this 5-10 years ago... so please anyone who knows better feel free to correct my statements. | |
|
Ravi FernandoProject administrator
Volunteer tester
Project scientist
Send message
Joined: 21 Mar 19
Posts: 211
ID: 1108183
Credit: 13,824,824
RAC: 7,626
|
|
Good points, wolfemancs. (The covering set for 78557 is {3, 5, 7, 13, 19, 37, 73}.) A few comments, with apologies in advance for the pedantry:
All known Sierpinski numbers have a fairly small covering set.
Not quite: some Sierpinski numbers, such as 44745755^4, rely on algebraic factorizations combined with partial covering sets. JeppeSN discusses this here. But this can only happen when k is a perfect power, and none of the SoB k's fit that description.
All the ks remaining in SoB have been proven to NOT have a covering set of any size.
I think this is *technically* false. It's known that all SoB k's produce primes in the dual Sierpinski project, i.e. primes of the form 2^n + k. Any covering set for k in SoB is also a covering set in the dual Sierpinski problem. But technically, having a covering set doesn't mean you produce no primes--it means you produce no primes except possibly for the primes in the covering set. So e.g. k=67607 is known to produce at least two primes (or maybe PRPs, not sure if they've been tested with ECPP): 2^16389 + 67607 and 2^46549 + 67607. It follows that any covering set for k=67607 would need to include both of these rather large primes. It seems very unlikely that such a covering set exists, but I don't know how to prove that it doesn't. | |
|
BurVolunteer tester
Send message
Joined: 25 Feb 20
Posts: 515
ID: 1241833
Credit: 414,481,880
RAC: 219
|
|
Thank you for that detailed answer, that was exactly what I was hoping for. Unfortunately, I doubt I will even get a glimpse of why things are that way - the paper you quoted for example - but I really enjoy reading explanations such as yours.
98%, 80%, 98.5%, 99.6%, and 76% chances respectively of producing primes below the current leading edge.) But there are a lot of odd numbers 1 < k < 78557, so it's not surprising that five of them have been "unlucky". That means, there are say 100 k's with a 98% chance of generating a prime with n < 14M, so finding 2 where it's larger was to be expected?
asymptotically we expect a given k to produce about X primes below n = 2^(X/weight) I'm not sure I got that, to calculate X for a given weight and n I would rearrange to X = log2(n) * weight? And to calculate at which n a given k probably produces a prime is done by X = 1?
All the ks remaining in SoB have been proven to NOT have a covering set of any size. I thought exactly that was NOT proven. Because otherwise we'd already know they aren't Sierpinski numbers? Having a covering set is a necessary requirement for a Sierpinski number, I think.
Or do I get the nature of "covering set" wrong? I think it means every number produced by that k will be divisible by at least one of the members of the set. So that k cannot produce a prime because if it's divisible by a member of the set it isn't a prime.
If it is prove a k does not have a covering set of any size, that means that the k can produce numbers that aren't divisible by any number than themselves, i.e. a prime and so it's not a Sierpinski number. | |
|
|
|
All the ks remaining in SoB have been proven to NOT have a covering set of any size. I thought exactly that was NOT proven.
It is not proved that they do not have a covering set, but it would have to consist of (unrealistically?) many and large primes.
Because otherwise we'd already know they aren't Sierpinski numbers? Having a covering set is a necessary requirement for a Sierpinski number, I think.
Not proved.
Most numbers that we can prove Sierpiński, have a covering set. As Ravi said, some numbers k that we can prove Sierpiński, have instead a combination of algebraic factorizations and a prime set that only "covers" the remaining cases for the exponent. This happens in many cases where k is a perfect power.
But: We have no proof that some crazy k could not be Sierpiński without matching the above description of numbers that we can prove Sierpiński.
Or do I get the nature of "covering set" wrong? I think it means every number produced by that k will be divisible by at least one of the members of the set. So that k cannot produce a prime because if it's divisible by a member of the set it isn't a prime.
That is correct.
If it is prove a k does not have a covering set of any size, that means that the k can produce numbers that aren't divisible by any number than themselves, i.e. a prime and so it's not a Sierpinski number.
No, see above. We do not know that there cannot exist a k that produces no prime for other reasons than covering sets, or algebraic factorizations.
/JeppeSN | |
|
Ravi FernandoProject administrator
Volunteer tester
Project scientist
Send message
Joined: 21 Mar 19
Posts: 211
ID: 1108183
Credit: 13,824,824
RAC: 7,626
|
Or do I get the nature of "covering set" wrong? I think it means every number produced by that k will be divisible by at least one of the members of the set. So that k cannot produce a prime because if it's divisible by a member of the set it isn't a prime.
Another technical point: if k*2^n + 1 is divisible by a member of your covering set, that doesn't entirely guarantee that it's not prime. After all, every prime is divisible by itself. In fact, if you're okay with "covering sets" being infinite, the set of all primes is a covering set for every k! (Proof: for all k and all n, k*2^n + 1 is greater than 1, so it's divisible by (and possibly equal to) some prime.) But of course not all k's are Sierpinski numbers.
For this reason, it's best to consider only finite covering sets. In this case, it's believed (but I think not proved) that some Sierpinski numbers with algebraic factorizations have no (finite) covering set. JeppeSN asked recently whether it's possible to construct a k that has a covering set but nonetheless produces at least one prime k*2^n + 1 (which would necessarily be an element of the covering set). I have no idea whether it's possible, but I don't see any obvious reason it isn't. | |
|
|
|
|
Ravi Fernando wrote: So e.g. k=67607 is known to produce at least two primes (or maybe PRPs, not sure if they've been tested with ECPP): 2^16389 + 67607 and 2^46549 + 67607.
It appears the first of these two numbers was proven prime just 2 months ago: http://factordb.com/index.php?id=1100000000537223829.
____________
1 PPSE (+2 DC) & 5 SGS primes | |
|
dukebgVolunteer tester
Send message
Joined: 21 Nov 17
Posts: 242
ID: 950482
Credit: 23,670,125
RAC: 0
                
|
Ravi Fernando wrote: So e.g. k=67607 is known to produce at least two primes (or maybe PRPs, not sure if they've been tested with ECPP): 2^16389 + 67607 and 2^46549 + 67607.
It appears the first of these two numbers was proven prime just 2 months ago: http://factordb.com/index.php?id=1100000000537223829.
Oh, that was most likely a lucky happenstance. Masaki UKAI runs ECPP basically for all PRPs in FDB of that size. 4.9K dd is pretty small, just few hours on modern hardware. I don't think they ran this exact number on purpose. | |
|
dukebgVolunteer tester
Send message
Joined: 21 Nov 17
Posts: 242
ID: 950482
Credit: 23,670,125
RAC: 0
|
|
A more on-topic message.
I started typing a message about why would the covering set from the dual problem automatically become a covering set in the "non-dual" problem. But then I figured it out on my own. Fun math.
| |
|
BurVolunteer tester
Send message
Joined: 25 Feb 20
Posts: 515
ID: 1241833
Credit: 414,481,880
RAC: 219
|
|
About the weight estimator, even with the help of the linked paper I couldn't figure out what N and P are.
Is N the number of results for the sequence k*2^n+1 we want to consider? But wouldn't that be identical to n? And P is the largest prime to consider?
For example if I wanted to estimate how many primes occur within the first 1M results of 5*2^n+1, what would I plug into the website? And is using X = log2(n)*weight the correct way to determine the number of primes? | |
|
Ravi FernandoProject administrator
Volunteer tester
Project scientist
Send message
Joined: 21 Mar 19
Posts: 211
ID: 1108183
Credit: 13,824,824
RAC: 7,626
|
About the weight estimator, even with the help of the linked paper I couldn't figure out what N and P are.
Yves can correct me if I have any of this wrong, but I believe the calculator estimates the weight of k by counting how many n's between 1 and N are not sieved out by primes less than P. In any case, their only effect on the calculation is that increasing P and N makes the calculation slower and more accurate. The default values are pretty good, and multiplying them by 10 or so will give a little more accuracy.
And is using X = log2(n)*weight the correct way to determine the number of primes?
That's a reasonable heuristic, at least if n is big enough. I haven't checked this against the data, but the following is probably a little more accurate in general: the number of primes with min < n < max should behave like a Poisson random variable with parameter log2((max + log2(k))/(min + log2(k))) * weight. (For a Poisson random variable, parameter = mean = variance.) The log2(k) terms are often negligible, but if k is large and you're starting at min = 1, then it's probably better to leave them in. | |
|
Message boards :
Seventeen or Bust :
Are people even sure 78557 is the smallest k? |
