As of writing, 2^82,589,933 − 1 is the largest known prime, but do we know all of the primes lower than it? If not, what is the largest known prime in sequence, without gaps?
Ask HN: What is the largest known prime in sequence?
1–9 of 9 posts
Re: Ask HN: What is the largest known prime in sequence?
#2Is it possible to verify a prime without knowing all smaller primes by corollary at least?
Re: Ask HN: What is the largest known prime in sequence?
#3Is it possible to verify a prime without knowing all smaller primes by corollary at least?
Yes. Very few (no?) primality tests require knowing or learning all primes up to the number being tested. Even trial division (the most simplistic test), you can stop looking for potential divisors once you pass sqrt(n), you learn nothing about most numbers up to n.
Re: Ask HN: What is the largest known prime in sequence?
#4We certainly do not know all primes lower than it. Our universe could not contain the answer of writing them all out.
I'm not sure the answer of the second part.
Re: Ask HN: What is the largest known prime in sequence?
#5Is it possible to verify a prime without knowing all smaller primes by corollary at least?
Yes. Very few (no?) primality tests require knowing or learning all primes up to the number being tested. Even trial division (the most simplistic test), you can stop looking for potential divisors once you pass sqrt(n), you learn nothing about most numbers up to n.
Oh yes good point! :facepalm:
Re: Ask HN: What is the largest known prime in sequence?
#6This [1] is a good comment explaining why we will never know all the primes up to the largest known prime.
I am having a surprisingly hard time finding the answer to the second part of your question. This site [2] samples the first 50 million primes, and the OEIS tracks this sequence as A000040 [3] but they provide a very short list. No luck finding the longest computed A000040 sequence so far.
EDIT:
The research on the Golbach Conjecture summarized here [4] found all the primes up to 10^18, that is the most I am finding so far.
[1]: https://www.reddit.com/r/math/comments/21nclc/comment/cgepan...
Re: Ask HN: What is the largest known prime in sequence?
#7[deleted]
Re: Ask HN: What is the largest known prime in sequence?
#8For Mersenne primes M(57 885 161) is the largest without a gap [0]
There is tracking of these [1]
[0] https://www.mersenneforum.org/showthread.php?p=595056#post59...
Re: Ask HN: What is the largest known prime in sequence?
#9Is it possible to verify a prime without knowing all smaller primes by corollary at least?
Yes. Very few (no?) primality tests require knowing or learning all primes up to the number being tested. Even trial division (the most simplistic test), you can stop looking for potential divisors once you pass sqrt(n), you learn nothing about most numbers up to n.
It’s even worse: to check whether a given number n is prime, you don’t need to know any prime.
If you do trial division in increasing order, you’ll find one (the smallest prime factor if n, which is n itself if n is prime), but if n is composite, you can avoid that by doing it in random order, or by starting near √n and working down (or up). That way, even if n has only two/three prime factors, you’ll find them/one of them, but that won’t tell you that they are/one of them is prime.