## Other

drummers-lowrise

Message boards : General discussion : Number of prime numbers found

Author Message
Michael_Osgroot

Joined: 31 Jul 21
Posts: 2
ID: 1399829
Credit: 25,637,345
RAC: 0

Message 151539 - Posted: 16 Sep 2021 | 13:08:11 UTC

I saw a video by Veritasium a while ago where they discussed The Collatz Conjecture. One thing that stood out is that they've tested every number up to 2^64 to see if if contradicts the conjecture.

This made me wonder: how far along are we for prime numbers? Is there an upper limit N for which we know for all numbers <n whether they are prime or not? If so, where is this upper limit and how quickly is it moving upwards?

Dave

Joined: 13 Feb 12
Posts: 3045
ID: 130544
Credit: 2,068,806,572
RAC: 1,065,591

Message 151542 - Posted: 16 Sep 2021 | 17:31:56 UTC - in response to Message 151539.

My understanding is 2^64 is computable & anything up to around 200 digits long is computable, but beyond that currently not Our projects focus on numbers of a particular form e.g k*2^n. A grand list of numbers is not exhaustable with current compute abilities.

Ravi Fernando
Volunteer tester
Project scientist

Joined: 21 Mar 19
Posts: 205
ID: 1108183
Credit: 11,783,358
RAC: 4,730

Message 151545 - Posted: 16 Sep 2021 | 20:51:31 UTC - in response to Message 151539.

Is there an upper limit N for which we know for all numbers <n whether they are prime or not? If so, where is this upper limit and how quickly is it moving upwards?

Depends on what you mean by "know". Does a prime count as "known" if a computer once checked that it's prime, but this information wasn't stored anywhere? If so, then N is probably at least 2^64, and maybe even an order of magnitude or two larger. But I think most of this information isn't stored anywhere, because it's so easy to recompute on the fly. The difficulty of finding all the primes up to (say) 10^25 isn't that it's hard to check whether a 25-digit number is prime or not; it's that doing anything 10^25 times takes a lot of work. And why bother? Probably no one* will ever care whether 7109827749198234719845111 is prime, and if they do then they can easily check it themselves.

In a different direction, it is known exactly how many primes there are up to 10^28--but this was calculated without listing the primes themselves. See here.

* (except for people reading this)

Grebuloner
Volunteer tester

Joined: 2 Nov 09
Posts: 441
ID: 49572
Credit: 2,380,071,112
RAC: 2,271,289

Message 151546 - Posted: 17 Sep 2021 | 5:10:09 UTC - in response to Message 151545.

Is there an upper limit N for which we know for all numbers <n whether they are prime or not? If so, where is this upper limit and how quickly is it moving upwards?

Depends on what you mean by "know". Does a prime count as "known" if a computer once checked that it's prime, but this information wasn't stored anywhere? If so, then N is probably at least 2^64, and maybe even an order of magnitude or two larger. But I think most of this information isn't stored anywhere, because it's so easy to recompute on the fly. The difficulty of finding all the primes up to (say) 10^25 isn't that it's hard to check whether a 25-digit number is prime or not; it's that doing anything 10^25 times takes a lot of work. And why bother? Probably no one* will ever care whether 7109827749198234719845111 is prime, and if they do then they can easily check it themselves.

In a different direction, it is known exactly how many primes there are up to 10^28--but this was calculated without listing the primes themselves. See here.

* (except for people reading this)

Just as a small exercise in curiosity, and really why these lists will never be compiled at all, I did a very rough estimation of the storage needed to store all of those individual values with minimal indexing.

Call it around 10^33 Zettabytes (ZB) = 10^42 TB. The current estimated total world data storage installation is just under 7 ZB.

For more giggles, if you were to use a 1TB microSD card (165mm^3), the current data storage density champion, just the cards would be 10^8 times the volume of the sun or 25% of that of Betelgeuse (but with the mass of a very large globular cluster, it might not be that big for long...).
____________
Eating more cheese on Thursdays.

Ravi Fernando
Volunteer tester
Project scientist

Joined: 21 Mar 19
Posts: 205
ID: 1108183
Credit: 11,783,358
RAC: 4,730

Message 151547 - Posted: 17 Sep 2021 | 5:31:50 UTC - in response to Message 151546.

Call it around 10^33 Zettabytes (ZB) = 10^42 TB. The current estimated total world data storage installation is just under 7 ZB.

Wait, 10^54 bytes to store about 10^26 28-digit numbers? They shouldn't take 10^28 bits each, unless you're storing them in tally marks.

Bur
Volunteer tester

Joined: 25 Feb 20
Posts: 511
ID: 1241833
Credit: 407,815,873
RAC: 10,359

Message 151550 - Posted: 17 Sep 2021 | 11:35:44 UTC - in response to Message 151539.

I was thinking along the same lines when I first got into prime searching. But I was met with the same explanations you got now and looking back, the question doesn't really make sense.

There isn't a hard border because proving primality just gets harder and harder with increasing size. A 40,000 digit number takes a year or so using the ECPP test. 3000 digits is easily doable on a normal computer in 1-2 days if I remember correctly.

You might note that these sizes are very small compared to what's being done at Primegrid. That's because they exploit specific properties of the primes, mostly the fact that the prime +1 or -1 is completely factored. I.e. for P = 3*2^1234567+1 we now that P-1 is 2^1234567*3. Then special tests that are much faster can be used. But it only works for those special numbers. Nobody can prove 3*2^1234567+87 to be prime or not.

To give some sort of satisfying answer (maybe), currently there is no software that is capable of proving if an _arbitrary_ number larger than 10^40,000 = 2^132877 is prime. So in a sense that's the limit we're at.

So searches like Primegrid or GIMPS are only about looking for individual record-size primes of special form. Not to get an exhaustive list that would be incredibly large.

And no, I didn't check if 3*2^1234567+87 has any trivial factors... ;)
____________
1281979 * 2^485014 + 1 is prime ... no further hits up to: n = 5,700,000

Michael_Osgroot

Joined: 31 Jul 21
Posts: 2
ID: 1399829
Credit: 25,637,345
RAC: 0

Message 151552 - Posted: 17 Sep 2021 | 12:49:51 UTC

Thanks for the responses everybody. This was really insightful!

Grebuloner
Volunteer tester

Joined: 2 Nov 09
Posts: 441
ID: 49572
Credit: 2,380,071,112
RAC: 2,271,289

Message 151556 - Posted: 17 Sep 2021 | 16:18:10 UTC - in response to Message 151547.

Call it around 10^33 Zettabytes (ZB) = 10^42 TB. The current estimated total world data storage installation is just under 7 ZB.

Wait, 10^54 bytes to store about 10^26 28-digit numbers? They shouldn't take 10^28 bits each, unless you're storing them in tally marks.

Oh poop. You're right. I was using 10^28 as number of digits, not 28. Too many exponents!

Comes to *only* 10^6 ZB, so, still ridiculously huge. Yikes.
____________
Eating more cheese on Thursdays.

JeppeSN

Joined: 5 Apr 14
Posts: 1695
ID: 306875
Credit: 40,800,650
RAC: 11,855

Message 151557 - Posted: 17 Sep 2021 | 16:39:27 UTC - in response to Message 151550.

Nobody can prove 3*2^1234567+87 to be prime or not.
[...]
And no, I didn't check if 3*2^1234567+87 has any trivial factors... ;)

That particular number has some small factors:
3
2687
3329
35126251

(That 3 is a factor may be seen without a computer, 3*[2^1234567+29].)

Even if such a number had no easy factors, it would be possible to do a PRP test on it. Such a test can have two outcomes:
(1) proven composite
(2) probable prime
In most cases you get (1), and then it is not true that "nobody can prove it to be prime or not", because in that case we can prove that it is not prime. If you get (2), you can attempt a bunch of other PRP tests, and in rare cases one of them will prove it is composite after all, and again you have certainty. But if several PRP tests say probable prime, then there is an extremely extremely high probability it is prime, and in that case nobody can prove if it is prime or not.

/JeppeSN

Message boards : General discussion : Number of prime numbers found