Largest prime representable in javascript

Question

In Javascript, the largest integer that can be represented exactly is Number.MAX_SAFE_INTEGER, with a value of $ 2^{53} - 1$. What is the largest prime value that fits under this value threshold? I cannot find a suitable reference for this value on the internet.

Answer 1

$9\,007\,199\,254\,740\,881$ is the largest prime less than or equal to $2^{53}$.

This number is mentioned in this context here and here.

Answer 2

$2^{53}-111 = 9007199254740881$ is the largest prime below $2^{53}$

The next prime is $2^{53}+5 =9007199254740997$ but JavaScript will not represent this correctly

Answer 3

In Wolfram Alpha, you can type in NextPrime[2^53 - 1, -1] and it will give you the answer: 9007199254740881.

It's of course not a JavaScript runtime engine that comes up with this answer; the Wolfram Alpha server sends your query to its Wolfram Mathematica installation, which then gives the answer, and the server converts it from the Mathematica notebook format to HTML.

The more interesting question is, I think, if a JavaScript program could come up with this answer. Since there are roughly $2.45 \times 10^{14}$ primes less than $2^{53}$ (even Mathematica can't give a precise answer to this query), the Eratosthenes sieve is out of the question.

I have on my computer a JavaScript program I got from somewhere, maybe GitHub. It uses trial division with a couple of basic optimizations, nothing sophisticated.

I asked it to factorize 9007199254740880. It took a full two seconds to give me the answer: $2^4 \times 5 \times 61 \times 23563 \times 78332027$. I don't dare ask it to factorize the odd numbers on either side of it.

So, if a JavaScript program can come up with this answer, it would require a sophisticated algorithm. EDIT: Simple trial division (stopping upon finding the least prime factor of a composite) can give the answer in a reasonable amount of time, as Wang Weixiu demonstrates in a "gist" he linked from a comment.

P.S. I think it also needs to be said that $2^{53} - 1$ is not prime. Even Mersenne himself somehow knew that's not prime, even though its smallest prime factor of 6361 would probably have been inaccessible even to a monk with all the time in the world.

Answer 4

I believe the question asks for the largest prime representable in JavaScript, instead of the largest prime less than $2^{53}$, which is trivial to calculate. From this perspective, I have to point out that the suggested method using Number.MAX_SAFE_INTEGER is not reliable in a strict sense. The information provided in the question regarding Number.MAX_SAFE_INTEGER had been inaccurate.

Actually, instead of being 'the largest integer that can be represented exactly', ECMAScript Language Specification explains that:

The value of Number.MAX_SAFE_INTEGER is the largest integer n such that n and n + 1 are both exactly representable as a Number value.

This statement only implies the fact that the integer $2^{53}$ alone cannot be exactly represented, and it does not suggest that all integers larger than that value cannot be represented. Therefore, merely from Number.MAX_SAFE_INTEGER we cannot easily decide the upper bound of representable integers.

So, to solve the problem, it is unavoidable that we look into the way how number values are described in JavaScript. According to the Language Specification on the Number Type, aside from special values NaN, Infinity and zero, all finite nonzero number values are described in the form $$\color{green}s \times \color{green}m \times 2^{\color{green}e}.$$ Where $\color{green}s$ is $+1$ or $-1$, $\color{green}m$, $\color{green}e$ are integers and $0 < \color{green}m < 2^{53}$, $-1074 \le \color{green}e \le 971$.

It is now clear to see that to get the largest prime, we should set $\color{green}s$ to $+1$. $\color{green}e$ cannot be negative, or the $2^{\color{green}e}$ factor would make the value smaller; and $\color{green}e$ cannot be positive, or the value would have a factor of $2$, not a prime; therefore $\color{green}e$ must be $0$. By choosing $\color{green}m$ to be an appropriate value, we are able to get any positive integer smaller than $2^{53}$.

Hence, we can say that the requested prime is $9007199254740881$. (The number can be obtained in JavaScript by simple trial division in a reasonable time. The code is shown here.)