## Other

drummers-lowrise

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

 Subscribe SortOldest firstNewest firstHighest rated posts first
Author Message
Bur
Volunteer tester

Joined: 25 Feb 20
Posts: 511
ID: 1241833
Credit: 408,659,181
RAC: 28,274

Message 139572 - Posted: 10 Apr 2020 | 6:59:47 UTC

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? :)

dannyridel
Volunteer tester

Joined: 3 Feb 19
Posts: 967
ID: 1097922
Credit: 39,789,204
RAC: 204,820

Message 139573 - Posted: 10 Apr 2020 | 7:16:13 UTC - in response to Message 139572.

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.
____________
My lucky number is 6219*2^3374198+1

Bur
Volunteer tester

Joined: 25 Feb 20
Posts: 511
ID: 1241833
Credit: 408,659,181
RAC: 28,274

Message 139574 - Posted: 10 Apr 2020 | 7:22:45 UTC

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.

dannyridel
Volunteer tester

Joined: 3 Feb 19
Posts: 967
ID: 1097922
Credit: 39,789,204
RAC: 204,820

Message 139575 - Posted: 10 Apr 2020 | 7:25:11 UTC - in response to Message 139574.

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.
____________
My lucky number is 6219*2^3374198+1

dannyridel
Volunteer tester

Joined: 3 Feb 19
Posts: 967
ID: 1097922
Credit: 39,789,204
RAC: 204,820

Message 139576 - Posted: 10 Apr 2020 | 7:35:42 UTC

____________
My lucky number is 6219*2^3374198+1

Bur
Volunteer tester

Joined: 25 Feb 20
Posts: 511
ID: 1241833
Credit: 408,659,181
RAC: 28,274

Message 139577 - Posted: 10 Apr 2020 | 7:40:12 UTC - in response to Message 139575.

At the time of writing, whenever that was, 10^19 was at least taking up non-negligible 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?

JeppeSN

Joined: 5 Apr 14
Posts: 1727
ID: 306875
Credit: 41,454,479
RAC: 13,295

Message 139582 - Posted: 10 Apr 2020 | 10:03:33 UTC

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

Bur
Volunteer tester

Joined: 25 Feb 20
Posts: 511
ID: 1241833
Credit: 408,659,181
RAC: 28,274

Message 139600 - Posted: 11 Apr 2020 | 5:31:36 UTC - in response to Message 139582.

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 ever-moving range because of the ever-increasing 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. ;)

dannyridel
Volunteer tester

Joined: 3 Feb 19
Posts: 967
ID: 1097922
Credit: 39,789,204
RAC: 204,820

Message 139602 - Posted: 11 Apr 2020 | 6:27:24 UTC - in response to Message 139600.

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.
____________
My lucky number is 6219*2^3374198+1

JeppeSN

Joined: 5 Apr 14
Posts: 1727
ID: 306875
Credit: 41,454,479
RAC: 13,295

Message 139606 - Posted: 11 Apr 2020 | 8:04:05 UTC

I should also say that the "form" of the prime matters when you decide if it is "trivial" or "a new find". The 1001-digit 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 P-1 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^4253-1 and 2^4423-1, and today 1000-digit 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" P-1 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

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