PrimeGrid
Please visit donation page to help the project cover running costs for this month

Toggle Menu

Join PrimeGrid

Returning Participants

Community

Leader Boards

Results

Other

drummers-lowrise

Advanced search

Message boards : General discussion : Number of prime numbers found

Author Message
Michael_Osgroot
Send message
Joined: 31 Jul 21
Posts: 2
ID: 1399829
Credit: 25,637,345
RAC: 0
Cullen LLR Bronze: Earned 10,000 credits (54,022)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (45,212)PPS LLR Silver: Earned 100,000 credits (322,607)PSP LLR Silver: Earned 100,000 credits (163,527)SoB LLR Bronze: Earned 10,000 credits (85,120)TRP LLR Bronze: Earned 10,000 credits (14,691)Woodall LLR Bronze: Earned 10,000 credits (25,276)PPS Sieve Sapphire: Earned 20,000,000 credits (20,583,326)AP 26/27 Bronze: Earned 10,000 credits (32,344)GFN Ruby: Earned 2,000,000 credits (4,295,610)
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?

Profile DaveProject donor
Avatar
Send message
Joined: 13 Feb 12
Posts: 3045
ID: 130544
Credit: 2,068,806,572
RAC: 1,065,591
Found 2 primes in the 2018 Tour de PrimesFound 1 prime in the 2020 Tour de Primes321 LLR Jade: Earned 10,000,000 credits (10,055,017)Cullen LLR Jade: Earned 10,000,000 credits (10,149,898)ESP LLR Jade: Earned 10,000,000 credits (10,091,372)Generalized Cullen/Woodall LLR Jade: Earned 10,000,000 credits (10,150,401)PPS LLR Jade: Earned 10,000,000 credits (10,131,417)PSP LLR Jade: Earned 10,000,000 credits (10,098,246)SoB LLR Jade: Earned 10,000,000 credits (10,377,208)SR5 LLR Jade: Earned 10,000,000 credits (10,848,827)SGS LLR Jade: Earned 10,000,000 credits (10,023,596)TRP LLR Jade: Earned 10,000,000 credits (10,056,741)Woodall LLR Jade: Earned 10,000,000 credits (10,220,855)321 Sieve (suspended) Jade: Earned 10,000,000 credits (10,003,334)Cullen/Woodall Sieve (suspended) Silver: Earned 100,000 credits (268,250)Generalized Cullen/Woodall Sieve (suspended) Jade: Earned 10,000,000 credits (10,000,502)PPS Sieve Double Silver: Earned 200,000,000 credits (310,223,017)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Jade: Earned 10,000,000 credits (10,000,133)TRP Sieve (suspended) Jade: Earned 10,000,000 credits (10,000,970)AP 26/27 Double Silver: Earned 200,000,000 credits (206,395,150)GFN Double Silver: Earned 200,000,000 credits (204,159,637)WW Double Gold: Earned 500,000,000 credits (995,552,000)PSA Double Silver: Earned 200,000,000 credits (200,000,001)
Message 151542 - Posted: 16 Sep 2021 | 17:31:56 UTC - in response to Message 151539.
Last modified: 16 Sep 2021 | 17:32:11 UTC

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
Project administrator
Volunteer tester
Project scientist
Send message
Joined: 21 Mar 19
Posts: 205
ID: 1108183
Credit: 11,783,358
RAC: 4,730
321 LLR Gold: Earned 500,000 credits (942,037)Cullen LLR Bronze: Earned 10,000 credits (82,217)ESP LLR Bronze: Earned 10,000 credits (16,570)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (68,801)PPS LLR Ruby: Earned 2,000,000 credits (3,930,008)PSP LLR Silver: Earned 100,000 credits (106,263)SoB LLR Silver: Earned 100,000 credits (258,849)SR5 LLR Bronze: Earned 10,000 credits (76,537)SGS LLR Silver: Earned 100,000 credits (148,878)TRP LLR Silver: Earned 100,000 credits (195,905)Woodall LLR Bronze: Earned 10,000 credits (40,424)321 Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,001,667)AP 26/27 Bronze: Earned 10,000 credits (72,774)GFN Gold: Earned 500,000 credits (824,200)WW Bronze: Earned 10,000 credits (12,000)
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)

Profile GrebulonerProject donor
Volunteer tester
Avatar
Send message
Joined: 2 Nov 09
Posts: 441
ID: 49572
Credit: 2,380,071,112
RAC: 2,271,289
Discovered 3 mega primesFound 2 primes in the 2018 Tour de PrimesFound 4 primes in the 2019 Tour de PrimesFound 3 primes in the 2020 Tour de PrimesFound 1 mega prime in the 2020 Tour de PrimesFound 4 primes in the 2021 Tour de PrimesFound 7 primes in the 2022 Tour de PrimesFound 1 mega prime in the 2022 Tour de Primes321 LLR Sapphire: Earned 20,000,000 credits (27,589,187)Cullen LLR Sapphire: Earned 20,000,000 credits (20,754,874)ESP LLR Sapphire: Earned 20,000,000 credits (20,453,074)Generalized Cullen/Woodall LLR Sapphire: Earned 20,000,000 credits (47,014,596)PPS LLR Emerald: Earned 50,000,000 credits (61,756,838)PSP LLR Sapphire: Earned 20,000,000 credits (20,571,669)SoB LLR Emerald: Earned 50,000,000 credits (50,873,282)SR5 LLR Sapphire: Earned 20,000,000 credits (23,807,284)SGS LLR Sapphire: Earned 20,000,000 credits (21,819,843)TRP LLR Sapphire: Earned 20,000,000 credits (20,191,201)Woodall LLR Sapphire: Earned 20,000,000 credits (20,376,385)321 Sieve (suspended) Emerald: Earned 50,000,000 credits (55,630,889)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,178,073)Generalized Cullen/Woodall Sieve (suspended) Emerald: Earned 50,000,000 credits (56,046,594)PPS Sieve Double Gold: Earned 500,000,000 credits (521,014,891)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Turquoise: Earned 5,000,000 credits (9,468,384)TRP Sieve (suspended) Jade: Earned 10,000,000 credits (10,076,645)AP 26/27 Double Gold: Earned 500,000,000 credits (502,006,216)GFN Double Silver: Earned 200,000,000 credits (278,220,852)WW Double Silver: Earned 200,000,000 credits (482,028,000)PSA Double Bronze: Earned 100,000,000 credits (126,200,096)
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
Project administrator
Volunteer tester
Project scientist
Send message
Joined: 21 Mar 19
Posts: 205
ID: 1108183
Credit: 11,783,358
RAC: 4,730
321 LLR Gold: Earned 500,000 credits (942,037)Cullen LLR Bronze: Earned 10,000 credits (82,217)ESP LLR Bronze: Earned 10,000 credits (16,570)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (68,801)PPS LLR Ruby: Earned 2,000,000 credits (3,930,008)PSP LLR Silver: Earned 100,000 credits (106,263)SoB LLR Silver: Earned 100,000 credits (258,849)SR5 LLR Bronze: Earned 10,000 credits (76,537)SGS LLR Silver: Earned 100,000 credits (148,878)TRP LLR Silver: Earned 100,000 credits (195,905)Woodall LLR Bronze: Earned 10,000 credits (40,424)321 Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,001,667)AP 26/27 Bronze: Earned 10,000 credits (72,774)GFN Gold: Earned 500,000 credits (824,200)WW Bronze: Earned 10,000 credits (12,000)
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.

Profile BurProject donor
Volunteer tester
Avatar
Send message
Joined: 25 Feb 20
Posts: 511
ID: 1241833
Credit: 407,815,873
RAC: 10,359
321 LLR Ruby: Earned 2,000,000 credits (2,092,823)Cullen LLR Ruby: Earned 2,000,000 credits (2,315,295)ESP LLR Ruby: Earned 2,000,000 credits (2,151,088)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,620,968)PPS LLR Jade: Earned 10,000,000 credits (10,943,107)PSP LLR Ruby: Earned 2,000,000 credits (2,064,832)SoB LLR Ruby: Earned 2,000,000 credits (2,434,466)SR5 LLR Ruby: Earned 2,000,000 credits (2,065,004)SGS LLR Ruby: Earned 2,000,000 credits (2,027,649)TRP LLR Ruby: Earned 2,000,000 credits (2,089,856)Woodall LLR Ruby: Earned 2,000,000 credits (2,112,258)321 Sieve (suspended) Ruby: Earned 2,000,000 credits (2,107,153)PPS Sieve Turquoise: Earned 5,000,000 credits (5,096,952)AP 26/27 Turquoise: Earned 5,000,000 credits (5,797,662)GFN Jade: Earned 10,000,000 credits (10,874,159)WW Double Silver: Earned 200,000,000 credits (349,980,000)PSA Amethyst: Earned 1,000,000 credits (1,042,601)
Message 151550 - Posted: 17 Sep 2021 | 11:35:44 UTC - in response to Message 151539.
Last modified: 17 Sep 2021 | 11:37:07 UTC

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
Send message
Joined: 31 Jul 21
Posts: 2
ID: 1399829
Credit: 25,637,345
RAC: 0
Cullen LLR Bronze: Earned 10,000 credits (54,022)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (45,212)PPS LLR Silver: Earned 100,000 credits (322,607)PSP LLR Silver: Earned 100,000 credits (163,527)SoB LLR Bronze: Earned 10,000 credits (85,120)TRP LLR Bronze: Earned 10,000 credits (14,691)Woodall LLR Bronze: Earned 10,000 credits (25,276)PPS Sieve Sapphire: Earned 20,000,000 credits (20,583,326)AP 26/27 Bronze: Earned 10,000 credits (32,344)GFN Ruby: Earned 2,000,000 credits (4,295,610)
Message 151552 - Posted: 17 Sep 2021 | 12:49:51 UTC

Thanks for the responses everybody. This was really insightful!

Profile GrebulonerProject donor
Volunteer tester
Avatar
Send message
Joined: 2 Nov 09
Posts: 441
ID: 49572
Credit: 2,380,071,112
RAC: 2,271,289
Discovered 3 mega primesFound 2 primes in the 2018 Tour de PrimesFound 4 primes in the 2019 Tour de PrimesFound 3 primes in the 2020 Tour de PrimesFound 1 mega prime in the 2020 Tour de PrimesFound 4 primes in the 2021 Tour de PrimesFound 7 primes in the 2022 Tour de PrimesFound 1 mega prime in the 2022 Tour de Primes321 LLR Sapphire: Earned 20,000,000 credits (27,589,187)Cullen LLR Sapphire: Earned 20,000,000 credits (20,754,874)ESP LLR Sapphire: Earned 20,000,000 credits (20,453,074)Generalized Cullen/Woodall LLR Sapphire: Earned 20,000,000 credits (47,014,596)PPS LLR Emerald: Earned 50,000,000 credits (61,756,838)PSP LLR Sapphire: Earned 20,000,000 credits (20,571,669)SoB LLR Emerald: Earned 50,000,000 credits (50,873,282)SR5 LLR Sapphire: Earned 20,000,000 credits (23,807,284)SGS LLR Sapphire: Earned 20,000,000 credits (21,819,843)TRP LLR Sapphire: Earned 20,000,000 credits (20,191,201)Woodall LLR Sapphire: Earned 20,000,000 credits (20,376,385)321 Sieve (suspended) Emerald: Earned 50,000,000 credits (55,630,889)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,178,073)Generalized Cullen/Woodall Sieve (suspended) Emerald: Earned 50,000,000 credits (56,046,594)PPS Sieve Double Gold: Earned 500,000,000 credits (521,014,891)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Turquoise: Earned 5,000,000 credits (9,468,384)TRP Sieve (suspended) Jade: Earned 10,000,000 credits (10,076,645)AP 26/27 Double Gold: Earned 500,000,000 credits (502,006,216)GFN Double Silver: Earned 200,000,000 credits (278,220,852)WW Double Silver: Earned 200,000,000 credits (482,028,000)PSA Double Bronze: Earned 100,000,000 credits (126,200,096)
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.

Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1695
ID: 306875
Credit: 40,800,650
RAC: 11,855
Found 1 prime in the 2020 Tour de Primes321 LLR Gold: Earned 500,000 credits (593,283)Cullen LLR Gold: Earned 500,000 credits (611,298)ESP LLR Silver: Earned 100,000 credits (174,818)Generalized Cullen/Woodall LLR Silver: Earned 100,000 credits (112,799)PPS LLR Jade: Earned 10,000,000 credits (15,959,415)PSP LLR Silver: Earned 100,000 credits (428,457)SoB LLR Silver: Earned 100,000 credits (466,812)SR5 LLR Silver: Earned 100,000 credits (210,142)SGS LLR Silver: Earned 100,000 credits (112,277)TRP LLR Silver: Earned 100,000 credits (342,501)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve (suspended) Silver: Earned 100,000 credits (175,037)PPS Sieve Bronze: Earned 10,000 credits (10,113)AP 26/27 Bronze: Earned 10,000 credits (12,129)GFN Ruby: Earned 2,000,000 credits (4,228,147)WW Turquoise: Earned 5,000,000 credits (9,640,000)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
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... ;)

Some comments on this.

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

Post to thread

Message boards : General discussion : Number of prime numbers found

[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2022 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 2.79, 2.92, 2.88
Generated 4 Jul 2022 | 2:04:32 UTC