6

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.

G987
  • 61
  • 1
    Note that this is not the "largest representable value", but the largest integer such that it and all (absolutely) smaller integers can be represented exactly. (For example $2^{53}+2$ can be represented too). – hmakholm left over Monica Jul 04 '19 at 09:47
  • Thanks for the heads up, I edited the question accordingly – G987 Jul 04 '19 at 11:35
  • 2
    The description is still slightly off, because $2^{53}$ can be represented exactly. (It is not clear to me why JavaScript thinks it is an "unsafe" integer; I suspect it is simply a mistake by the people who first introduced the MAX_SAFE_INTEGER constant). – hmakholm left over Monica Jul 04 '19 at 12:14
  • @BillThomas: Of course it can be done in JS, after all it's just an algorithm, therefore implementable in about any programming language. Begin with $2^{53}-1$ and apply any of the many primality tests available: if the tested number is prime, stop; if not, decrease by $2$ (because even numbers $\ne 2$ have no chance of being prime, so you may skip them) and repeat. The exact JS code to do this, though, is probably besides the scope of MSE. – Alex M. Jul 11 '19 at 16:27
  • 1
    @AlexM. Yeah, it would be besides the scope. However, it would be in scope to say something like "It took me a couple of minutes to write up the JS code and even less time than that for it to come up with the right answer." Mwahahahaha! – The Short One Jul 12 '19 at 21:39
  • Having thought about it for a few days, I challenge the claim that a number near $2^{53}$ is "the largest integer that can be represented exactly" "in JavaScript". JavaScript is readily able to represent much larger integers using the Chinese Remainder Theorem with multiple moduli. Also, JavaScript has BigInt. – Eric Towers Jul 21 '19 at 17:18

4 Answers4

6

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

Wang Weixuan
  • 470
  • 3
    Please tell us how many seconds it took your Web browser or Node.js to come up with $9007199254740881$ using your JavaScript code. – The Short One Jul 15 '19 at 21:28
  • 2
    @TheShortOne It took me around half a second on my MacBook. Code here: https://gitlab.com/snippets/1875549 – Wang Weixuan Jul 15 '19 at 23:59
  • 2
    Took a full second on my computer, and Firefox complained that a page was slowing down the browser, but then it gave the result. I think I'm going to have to revise my own answer. – Robert Soupe Jul 16 '19 at 04:54
  • 1
    For what it's worth, I think you should integrate your comment into your answer. I'd give you the bounty anyway, but it's not up to me. – David R. Jul 16 '19 at 22:10
5

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.

Robert Soupe
  • 14,663
  • Mersenne divisors have to be of form 2kp+1 with k congruent 0,-p mod 4. With a proof of this it sieves it down to just, 60 values to test as factors. most of which will likely have small factors. –  Jul 05 '19 at 16:15
  • @RoddyMacPhee Yeah, okay, you know that, but did Mersenne? – Robert Soupe Jul 06 '19 at 00:20
  • Euler, supposedly used it or similar things, to prove M31 prime. Also just use the $2^{53}-1$ as a base $2^{53}$ digit. –  Jul 06 '19 at 00:24
  • 2
    Okay fine, it's an ancillary detail I now regret having even mentioned. – Robert Soupe Jul 06 '19 at 00:25
  • 1
    Just another tiny bit of trivia: The number of primes smaller than $2^{53}$ is precisely $252252704148404$. – Peter Košinár Jul 12 '19 at 13:59
2

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

Eric Towers
  • 67,037
1

$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

Henry
  • 157,058