Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummerslowrise

Message boards :
General discussion :
Largest prime where all smaller primes are known
Author 
Message 
BurVolunteer tester
Send message
Joined: 25 Feb 20 Posts: 332 ID: 1241833 Credit: 22,611,276 RAC: 4,081

To rephrase the title, up to what number have we found all primes?
Finding new large primes is nice, but I feel like this is just picking one prime here and there while the vast majority is still unknown. I know this is done because efficient primality tests exist for these number. How long would a desktop PC take to determine primality of a number with a magnitude of e.g. 10^9?
Using the x/(ln(x)1) approximation, up to 10^9 there are about 50 million primes and up to 10^12 there are 38 billion primes. I would assume they are all known, but are they? :)  


I think primegen tried this about a decade ago, and somehow that provable unattainable, so I don't think this would be a good idea.
Here's a link to PrimeGen's purpose.
____________
SHSID Electronics Group
SHSIDElectronicsGroup@outlook.com
GFN14: 50103906^16384+1
Proth "SoB": 44243*2^440969+1
 

BurVolunteer tester
Send message
Joined: 25 Feb 20 Posts: 332 ID: 1241833 Credit: 22,611,276 RAC: 4,081

Thanks, Primgen had some useful information. Apparently it took a Pentium II only 8 s to find all primes up to 10^9.
So I guess we have proceeded a lot farther than that.
Maybe there's not much use in finding all primes in a given range (on the other hand, are large primes useful?), but at least it could maybe tell us something about the distribution of primes and how closely they follow x(ln(x)? Is really no one working on this publicly?
edit: I found this site with all primes up to 10^12.  


About this, I think every time you run an "Amicable Numbers" task, you have to calculate and store all primes below 10^11. That takes around a minute on Zen 1 mobile.
____________
SHSID Electronics Group
SHSIDElectronicsGroup@outlook.com
GFN14: 50103906^16384+1
Proth "SoB": 44243*2^440969+1
 


And here is the answer to the question you were asking.
____________
SHSID Electronics Group
SHSIDElectronicsGroup@outlook.com
GFN14: 50103906^16384+1
Proth "SoB": 44243*2^440969+1
 

BurVolunteer tester
Send message
Joined: 25 Feb 20 Posts: 332 ID: 1241833 Credit: 22,611,276 RAC: 4,081

I also found this article.
At the time of writing, whenever that was, 10^19 was at least taking up nonnegligible time for computation.
What I don't get is this quote:
If we could give the smallest number n such that it is not known whether or not n is prime, then someone could check the next million primes in about a second of computer time (at most!)
Is this true? Wouldn't it depend on how large n is?  


For such small primes, it really makes no sense to say which are "known" and which are not. Because it is extremely fast to test them, or find ranges of them by sieving.
For example, is the prime 123456789012419 known or not? Maybe someone with no interesting use for his disk space keeps a list of all primes up to this one? Otherwise, people have been sieving with this prime several times when sieving huge prime candidates of specific forms.
In any case, I can quickly find a prime like 123456789012419 again and again.
With the algorithms currently known, I can say more or less the same about much larger numbers. For example: 19274977647524045137176747261631187746108415626215325229208489430965464346826475939625734103100337620741385531281753006461219071364885762542087024324487417226115617524799488208682101513979132916210796814405170532841180456692645865935253160621642870250695588758055828781944984410800243831045972256652775296930985068201892919470097171237969667440025114747327301493864809266891116920128215548495811103587777501640289217786337247461123285453493305495576420471292946357150373935492857581578634258121054898834637310908005588813846155779237708147215620114352048942891758044711658313395487618062145141330152109201725524175045359043836313030302133790270048555942260587698367477221629047609315851989938692954145536698585567964765973246897264896248409655729427702349105577352059439358905597587630036194681573105140397557930800173501867184618943742721151333397726094420959544404008593525833938211500864129520164165197729018455605553138095373434396001812004389826823405857997063855903817737712419747133204592663989 is a prime number I just picked at random. It is probably not "known", but because I picked it and mentioned it here, is it "known" now? Nobody is going to remember this number, because you can always just pick another prime of this size any time you like.
/JeppeSN  

BurVolunteer tester
Send message
Joined: 25 Feb 20 Posts: 332 ID: 1241833 Credit: 22,611,276 RAC: 4,081

So let's say a prime is "known" if it is either stored somewhere or can be found computationally within a conveniently short amount of time (whatever that is).
Most would agree that, prior to their discovery the current large primes have not been known according to that definition. And 1927497764752404... can be considered known even before you posted it.
There has to be a range of numbers in between where primes change from known to unknown. But it's an evermoving range because of the everincreasing computer power. So I see now that my question didn't really make sense the way I thought it would.
But I'm still not really satisfied with saying, it doesn't make sense to generate primes in order because apparently it does make sense to determine the primality of individual large numbers. And not just THE largest prime but also way smaller primes just because they can be constructed in a specific way.
We could just as well say, let's find all primes between the third and the second largest Germaine prime. The only difference from what we do is that it would take much (much much?) more time to find those and thus we keep picking specific one.
In conclusion, don't get me wrong, I enjoy doing this project. ;)  


Well in the end, it comes down to the ethics and definition of a "known" prime. So i think this discussion might need a closing.
____________
SHSID Electronics Group
SHSIDElectronicsGroup@outlook.com
GFN14: 50103906^16384+1
Proth "SoB": 44243*2^440969+1
 


I should also say that the "form" of the prime matters when you decide if it is "trivial" or "a new find". The 1001digit prime I posted before, I found with PARI/GP with nextprime(random(10^1000)+10^1000). In fact that one only returns a probable prime. This prime has no special form, so it actually takes a couple of minutes to verify it (I just used isprime from PARI/GP).
For primes with no special form, see for example The Top Twenty: Elliptic Curve Primality Proof. So a bit under 22,000 digits is enough to make it to Top 20, and 40,000 digits is enough to be #1.
On the other hand, for primes P where it is trivial to factor P1 or P+1, we have much faster methods, and the threshold is higher. Already in November 1961, primes of special form with more than 1000 digits were found, namely the Mersenne primes 2^42531 and 2^44231, and today 1000digit primes of a nice form are totally trivial. To see where a prime of a particular size would go in on the Top 5000, check the graph at How Fast are the Primes Growing? You can see that an "arbitrary" P1 or P+1 prime that could just make the Top Fifty 20 years ago, is deemed uninteresting and "removed" from the list today (i.e. falls out of the Top 5000).
/JeppeSN  

Post to thread
Message boards :
General discussion :
Largest prime where all smaller primes are known 