5 ms·

Ask HN: What is the largest known prime in sequence?

10 points by joemaffei 5y ago

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?

vemodalen 5y ago
For 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#post595056 https://www.mersenneforum.org/showthread.php?p=595056#post59... [1] https://www.mersenne.org/report_milestones/ https://www.mersenne.org/report_milestones/
OJFord 5y ago
Is it possible to verify a prime without knowing all smaller primes by corollary at least?
- kadoban 5y ago
  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.
  - OJFord 5y ago
    Oh yes good point! :facepalm:
  - Someone 5y ago
    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.
kadoban 5y ago
We 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.
philomath_mn 5y ago
This [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/cgepane/?utm_source=share&utm_medium=web2x&context=3 https://www.reddit.com/r/math/comments/21nclc/comment/cgepan... [2]: https://primes.utm.edu/lists/small/millions/ https://primes.utm.edu/lists/small/millions/ [3]: https://oeis.org/A000040 https://oeis.org/A000040 [4]: http://sweet.ua.pt/tos/goldbach.html http://sweet.ua.pt/tos/goldbach.html
deleted 5y ago
[deleted]

10 points by joemaffei 5y ago

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?

vemodalen 5y ago

For 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#post595056 https://www.mersenneforum.org/showthread.php?p=595056#post59... [1] https://www.mersenne.org/report_milestones/ https://www.mersenne.org/report_milestones/

OJFord 5y ago

Is it possible to verify a prime without knowing all smaller primes by corollary at least?

kadoban 5y ago
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.
- OJFord 5y ago
  Oh yes good point! :facepalm:
- Someone 5y ago
  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.

kadoban 5y ago

We 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.

philomath_mn 5y ago

This [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/cgepane/?utm_source=share&utm_medium=web2x&context=3 https://www.reddit.com/r/math/comments/21nclc/comment/cgepan... [2]: https://primes.utm.edu/lists/small/millions/ https://primes.utm.edu/lists/small/millions/ [3]: https://oeis.org/A000040 https://oeis.org/A000040 [4]: http://sweet.ua.pt/tos/goldbach.html http://sweet.ua.pt/tos/goldbach.html

deleted 5y ago

[deleted]