6 ms·

so I didn't know this, but got curious about how many known prime there are - I knew there were infinite primes, but thought that there would be some concrete l

so I didn't know this, but got curious about how many known prime there are - I knew there were infinite primes, but thought that there would be some concrete list of all the primes that we had discovered somewhere - but apparently not https://math.stackexchange.com/questions/272791/how-many-prime-numbers-are-known https://math.stackexchange.com/questions/272791/how-many-pri... > Nobody's really keeping count. ... There are very many hundred-digit primes to find. We could cover the Earth in harddisks full of distinct hundred-digit primes to a height of hundreds of meters, without even making a dent in the supply of hundred-digit primes.

TheRealPomax 9y ago
That list would be as long as the list of "all even numbers" because any list of primes immediately gives you a next prime that should be on the list, but isn't, in the same way that having a list of even numbers immediately gives you the next even number that should be on that list but isn't: Given an ordered list of primes {2,3,5,...,n} one (of several) immediately known next prime number is simply (2 x 3 x 5 x ... x n) + 1. We know that number's prime because it cannot be cleanly divided by 2, or 3, or 5, or ..., or n. As such, even if it might be useful to have a list of all known primes, annotated with what kind of prime each number is, such a list cannot be constructed: even just the subset of all prime numbers generated based on the simple above rule would be infinitely long, just like the list of all even numbers is infinitely long.
kryptiskt 9y ago
RSA encryption keys uses the product of two large primes, where each prime is many digits long. So many new primes are "discovered" every day.
- schoen 9y ago
  Interestingly, those primes' primality is normally proven statistically rather than deductively. This is not really a practical issue for people using RSA, but could be a philosophical issue for someone interested in the question of how many different numbers' primality has been proven by humanity.
  - OscarCunningham 9y ago
    In fact if someone worked out how to crack RSA when it turned out that one of those numbers weren't prime then they would have invented a fast primality check. Which would be really cool in itself, and allow RSA to be fixed.
  - xamuel 9y ago
    When philosophers study mankind's knowledge, it's more typical to study the things mankind would ideally know at the end of all time assuming mankind could continue forever. (Formally: the knowledge predicate is usually assumed to satisfy modus ponens: if mankind knows "A implies B" and mankind knows "A", then mankind knows "B") Under this abstraction, if mankind knows the axioms of logic and Peano arithmetic, then mankind [ideally eventually] knows the primality of all primes. Contrast: Which Turing machines will mankind [ideally eventually] know are never-halting? This is a much harder question and the answer is probably not "all never-halting Turing machines"
    - schoen 9y ago
      It's a little funny that mankind gets to use a full-fledged infinite-tape Turing machine in order to compute arbitrarily large computations, since no such machine would fit in our universe. https://en.wikipedia.org/wiki/Limits_of_computation https://en.wikipedia.org/wiki/Limits_of_computation https://en.wikipedia.org/wiki/Transcomputational_problem https://en.wikipedia.org/wiki/Transcomputational_problem
      - deleted 9y ago
        [deleted]
      - fooker 9y ago
        The description of a Turing machine that can do arbitrarily large computations can be finite. See: Kolmogorov complexity.
        schoen 9y ago
raverbashing 9y ago
The relevant thing is not that's a prime (it's pretty trivial to find one), but a Mersenne Prime Primality testing is not trivial at those number sizes
- zeep 9y ago
  not really, it is very hard to test any very large number for primality... this project only test numbers that satisfy the Mersenne prime definition though... 9 of the 10 known largest primes are Mersenne prime numbers probably because there is more people testing these numbers. http://primes.utm.edu/largest.html#biggest http://primes.utm.edu/largest.html#biggest
  - schoen 9y ago
    But the biggest reason that the largest known primes have this form is that they are subject to a much faster special-form primality test. https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality... There's no known general-form primality test that is nearly as fast for numbers of corresponding sizes.
  - ehsankia 9y ago
    People test these because it's the easiest pattern we know of for constructing large primes. So if you want to maximize your chances of finding a large prime, you'll check for the mersenne form.
    - mygo 9y ago
      people test these because we have the technology to check if a large number of the Mersenne form is prime at a faster speed than numbers that do not conform.
OscarCunningham 9y ago
I also used to think that there weren't very many primes. But the prime number theorem says that the number of primes less than n is about n/log(n). The function log doesn't grow very fast, so a large proportion of numbers are prime. For example the number of primes less than 10^100 is 4*10^97. Primes are really really common.
- soVeryTired 9y ago
  Much more common than square numbers, for example. sum(1/n^2) converges, but sum(1/p) for p prime doesn't.
bmm6o 9y ago
Not only are there an infinite number of primes, there are so many that the inverse series diverges. That is, Sum 1/p_i is infinite.
emmelaich 9y ago
Reading the GIMPS forums, some think they've missed a few. The occurrence rate is surprisingly (or not?) irregular.
Someone 9y ago
RSA encryption (https://en.wikipedia.org/wiki/RSA_(cryptosystem) https://en.wikipedia.org/wiki/RSA_(cryptosystem), used in PGP, TLS certificates, among others) is based on the fact that I know a pair of primes you don’t know, so even if somebody tried to keep such a list, it better be incomplete.
seppel 9y ago
> but thought that there would be some concrete list of all the primes that we had discovered It is trivial (in computational power) to find a random prime in order of 2^2048. So such a list would be way to big to store somewhere and always be out of date. It is not hard to find very big primes. It is just hard to find very very big primes.
chimeracoder 9y ago
> so I didn't know this, but got curious about how many known prime there are This isn't the exact question you're asking, but we actually know the distribution of prime numbers, which allows us to calculate the (approximate) number of primes that are less than or equal to an arbitrary value. Since the largest prime discovered is 2^(277,232,917-1), that means that the number of primes less than or equal to that number is approximately equal to 2^(277,232,917-1)/ln(2^(277,232,917-1)). That's approximately equal to: 2^(277,232,917-1)/ln(2^(277,232,917)), which is in turn equal to 2^(277,232,917-1)/(277,232,917 * ln(2)). That's a number that's too big to plug into your standard everyday calculator, but that tells you the number of primes you could "discover" and still not break the (new) record.
- qmalzp 9y ago
  Nit: the largest prime discovered is 2^(277,232,917)-1 not 2^(277,232,917-1)
  - Franciscouzo 9y ago
    If you read the article, it's actually: (2^77,232,917)-1
    - TheRealPomax 9y ago
      Not sure if this was a serious comment, but if it was: due to operator precedence in mathematics, the expressions (2^77,232,917)-1, 2^(77,232,917)-1, and 2^77,232,917-1 are identically evaluated, with the parentheses only used to aid the human eye. This in contrast to 2^(77,232,917-1), which is 2^77,232,916 and is a very different number indeed.
      - deleted 9y ago
        [deleted]
      - kodablah 9y ago
        The parens are a red herring. GP is commenting on the previous poster using 277 instead of 77 (i.e. typo).

TheRealPomax 9y ago

That list would be as long as the list of "all even numbers" because any list of primes immediately gives you a next prime that should be on the list, but isn't, in the same way that having a list of even numbers immediately gives you the next even number that should be on that list but isn't: Given an ordered list of primes {2,3,5,...,n} one (of several) immediately known next prime number is simply (2 x 3 x 5 x ... x n) + 1. We know that number's prime because it cannot be cleanly divided by 2, or 3, or 5, or ..., or n. As such, even if it might be useful to have a list of all known primes, annotated with what kind of prime each number is, such a list cannot be constructed: even just the subset of all prime numbers generated based on the simple above rule would be infinitely long, just like the list of all even numbers is infinitely long.

kryptiskt 9y ago

RSA encryption keys uses the product of two large primes, where each prime is many digits long. So many new primes are "discovered" every day.

schoen 9y ago
Interestingly, those primes' primality is normally proven statistically rather than deductively. This is not really a practical issue for people using RSA, but could be a philosophical issue for someone interested in the question of how many different numbers' primality has been proven by humanity.
- OscarCunningham 9y ago
  In fact if someone worked out how to crack RSA when it turned out that one of those numbers weren't prime then they would have invented a fast primality check. Which would be really cool in itself, and allow RSA to be fixed.
- xamuel 9y ago
  When philosophers study mankind's knowledge, it's more typical to study the things mankind would ideally know at the end of all time assuming mankind could continue forever. (Formally: the knowledge predicate is usually assumed to satisfy modus ponens: if mankind knows "A implies B" and mankind knows "A", then mankind knows "B") Under this abstraction, if mankind knows the axioms of logic and Peano arithmetic, then mankind [ideally eventually] knows the primality of all primes. Contrast: Which Turing machines will mankind [ideally eventually] know are never-halting? This is a much harder question and the answer is probably not "all never-halting Turing machines"
  - schoen 9y ago
    It's a little funny that mankind gets to use a full-fledged infinite-tape Turing machine in order to compute arbitrarily large computations, since no such machine would fit in our universe. https://en.wikipedia.org/wiki/Limits_of_computation https://en.wikipedia.org/wiki/Limits_of_computation https://en.wikipedia.org/wiki/Transcomputational_problem https://en.wikipedia.org/wiki/Transcomputational_problem
    - deleted 9y ago
      [deleted]
    - fooker 9y ago
      The description of a Turing machine that can do arbitrarily large computations can be finite. See: Kolmogorov complexity.
      - schoen 9y ago

raverbashing 9y ago

The relevant thing is not that's a prime (it's pretty trivial to find one), but a Mersenne Prime Primality testing is not trivial at those number sizes

zeep 9y ago
not really, it is very hard to test any very large number for primality... this project only test numbers that satisfy the Mersenne prime definition though... 9 of the 10 known largest primes are Mersenne prime numbers probably because there is more people testing these numbers. http://primes.utm.edu/largest.html#biggest http://primes.utm.edu/largest.html#biggest
- schoen 9y ago
  But the biggest reason that the largest known primes have this form is that they are subject to a much faster special-form primality test. https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality... There's no known general-form primality test that is nearly as fast for numbers of corresponding sizes.
- ehsankia 9y ago
  People test these because it's the easiest pattern we know of for constructing large primes. So if you want to maximize your chances of finding a large prime, you'll check for the mersenne form.
  - mygo 9y ago
    people test these because we have the technology to check if a large number of the Mersenne form is prime at a faster speed than numbers that do not conform.

OscarCunningham 9y ago

I also used to think that there weren't very many primes. But the prime number theorem says that the number of primes less than n is about n/log(n). The function log doesn't grow very fast, so a large proportion of numbers are prime. For example the number of primes less than 10^100 is 4*10^97. Primes are really really common.

soVeryTired 9y ago
Much more common than square numbers, for example. sum(1/n^2) converges, but sum(1/p) for p prime doesn't.

bmm6o 9y ago

Not only are there an infinite number of primes, there are so many that the inverse series diverges. That is, Sum 1/p_i is infinite.

emmelaich 9y ago

Reading the GIMPS forums, some think they've missed a few. The occurrence rate is surprisingly (or not?) irregular.

Someone 9y ago

RSA encryption (https://en.wikipedia.org/wiki/RSA_(cryptosystem) https://en.wikipedia.org/wiki/RSA_(cryptosystem), used in PGP, TLS certificates, among others) is based on the fact that I know a pair of primes you don’t know, so even if somebody tried to keep such a list, it better be incomplete.

seppel 9y ago

> but thought that there would be some concrete list of all the primes that we had discovered It is trivial (in computational power) to find a random prime in order of 2^2048. So such a list would be way to big to store somewhere and always be out of date. It is not hard to find very big primes. It is just hard to find very very big primes.

chimeracoder 9y ago

> so I didn't know this, but got curious about how many known prime there are This isn't the exact question you're asking, but we actually know the distribution of prime numbers, which allows us to calculate the (approximate) number of primes that are less than or equal to an arbitrary value. Since the largest prime discovered is 2^(277,232,917-1), that means that the number of primes less than or equal to that number is approximately equal to 2^(277,232,917-1)/ln(2^(277,232,917-1)). That's approximately equal to: 2^(277,232,917-1)/ln(2^(277,232,917)), which is in turn equal to 2^(277,232,917-1)/(277,232,917 * ln(2)). That's a number that's too big to plug into your standard everyday calculator, but that tells you the number of primes you could "discover" and still not break the (new) record.

qmalzp 9y ago
Nit: the largest prime discovered is 2^(277,232,917)-1 not 2^(277,232,917-1)
- Franciscouzo 9y ago
  If you read the article, it's actually: (2^77,232,917)-1
  - TheRealPomax 9y ago
    Not sure if this was a serious comment, but if it was: due to operator precedence in mathematics, the expressions (2^77,232,917)-1, 2^(77,232,917)-1, and 2^77,232,917-1 are identically evaluated, with the parentheses only used to aid the human eye. This in contrast to 2^(77,232,917-1), which is 2^77,232,916 and is a very different number indeed.
    - deleted 9y ago
      [deleted]
    - kodablah 9y ago
      The parens are a red herring. GP is commenting on the previous poster using 277 instead of 77 (i.e. typo).