This is more of a curiosity than a research question, but I could not find it answered anywhere. What is the largest $N$ for which the statement in the title is true? I have recently read that the largest known prime is $2^{82589933} − 1$, but I imagine it is not known if, for example, $2^{82589933} − 3$ is prime. A closely related question: if $\pi(x)$ is the prime counting function, that is, $\pi(x)$ is the number of primes not exceeding $x$, what is the largest value of $n$ for which $\pi(n)$ is known exactly?
$\begingroup$
$\endgroup$
14
-
$\begingroup$ What is the "statement in the title"? It currently says "It is known if $n$ is prime for all $n \le N$", which, depending on the quantification, is never to rarely true. $\endgroup$– LSpiceCommented Jan 12, 2023 at 22:50
-
1$\begingroup$ @LSpice: the meaning is, what is the largest $N$ for which the primeness/compositeness of $n$ is "known" for all $n \leq N$. (I put "known" in quotes because I think it is hard to make this question precise... how could we in any sense "know" all numbers less than $2^{\textrm{large number}}$.) $\endgroup$– Sam HopkinsCommented Jan 12, 2023 at 22:55
-
3$\begingroup$ I suggest a new title: What is the smallest number for which we don't yet know primality? But since primality testing is polynomial time, the answer may quickly become obsolete. $\endgroup$– Joel David HamkinsCommented Jan 12, 2023 at 23:24
-
2$\begingroup$ @JoelDavidHamkins: yes, the fact that "PRIMES is in P" means the question does not really make sense. It's akin to the old "what's the smallest non-interesting number" chestnut... $\endgroup$– Sam HopkinsCommented Jan 12, 2023 at 23:26
-
2$\begingroup$ Valerio, you ask about whether we "can" decide primality for $n\leq N$, but we can decide primality for any number. If you mean to refer to which $N$ have we already done these tests, then if we knew such $N$, we could immediately increase it to $N+1$, and then $N+2$, and so on, for as much as want, since primality testing of any particular number is feasible. (Factoring is difficult; primality testing is easy.) $\endgroup$– Joel David HamkinsCommented Jan 13, 2023 at 1:18
|
Show 9 more comments
1 Answer
$\begingroup$
$\endgroup$
As explained in the comments, there is no well-defined answer to this question, because there is no organized effort to test primality of all numbers up to a certain bound.
However, there is a (more or less) well-defined answer (at any given point in time) to a related question: What is the largest $N$ for which the primality status of $2^n - 1$ is known for all $n\le N$? The answer, as of this writing, is 57885161 (though some "insiders" in the GIMPS project may be able to report a slightly higher number than that—but not higher than 74207281).
answered Jan 13, 2023 at 3:08