2
$\begingroup$

In JavaScript, the largest odd positive number representable is $2^{53}-1$. All integers between 1 and $2^{53}-1$ can be represented without loss of precision.

How many prime numbers can be represented in JavaScript? I know this can be approximated with the prime counting formula $\frac x{\ln x}$:

$$\frac{2^{53}}{\ln2^{53}}=\frac{2^{53}}{53\ln2}\approx 2.45\times10^{14}$$

How would one go about calculating an exact result?

$\endgroup$
2
  • $\begingroup$ You need to consult a list, there is no other way of doing so than 'counting' because we do not have a exact formula for $\pi(x)$. $\endgroup$
    – flawr
    Commented Dec 22, 2014 at 19:47
  • $\begingroup$ flawr, there are much faster ways than counting. See the Lehmer and LMO methods, for example. The latter can perform the calculation in ~30 seconds. See primecount on github, or Perl's ntheory for open source code. $\endgroup$
    – DanaJ
    Commented Dec 23, 2014 at 6:14

1 Answer 1

2
$\begingroup$

Evidently $$ \pi(2^{53}) = 252252704148404, $$ roughly $2.5 \cdot 10^{14}.$ Hmmm; since $2^{53}$ is composite, this is also your answer.

This is from a link off http://en.wikipedia.org/wiki/Prime-counting_function

To confirm the table and notation used, it is true that $\pi(2) = 1, $ $ \; \pi(4) = 2, $ $ \; \pi(8) = 4, $ $ \; \pi(16) = 6, $ $ \; \pi(32) = 11. $

# (c) 2012-2014, Tomás Oliveira e Silva
#
# See disclaimer in page
#   http://www.ieeta.pt/~tos/hobbies.html
#
# Do not bookmark this page, because its URI may change
# in the future. Instead, bookmark its parent page:
#   http://www.ieeta.pt/~tos/primes.html
#
# pi(x) is the number of primes not larger than x
# li(x) is the principal value of the integral of 1/log between 0 and x
# NbM is the exponential notation for the number N*2^M
#
# Last update made on November 20, 2012

   x                  pi(x)                      li(x)
---- ---------------------- -----------------------------
1b01                      1                      1.045...
1b02                      2                      2.967...
1b03                      4                      5.253...
1b04                      6                      8.519...
1b05                     11                     13.605...
1b06                     18                     21.934...
1b07                     31                     36.042...
1b08                     54                     60.513...
1b09                     97                    103.721...
1b10                    172                    181.078...
1b11                    309                    321.114...
1b12                    564                    576.922...
1b13                   1028                   1047.751...
1b14                   1900                   1919.888...
1b15                   3512                   3544.244...
1b16                   6542                   6583.986...
1b17                  12251                  12296.067...
1b18                  23000                  23069.193...
1b19                  43390                  43453.811...
1b20                  82025                  82137.527...
1b21                 155611                 155739.964...
1b22                 295947                 296113.838...
1b23                 564163                 564411.512...
1b24                1077871                1078221.700...
1b25                2063689                2063984.678...
1b26                3957809                3958349.548...
1b27                7603553                7604383.150...
1b28               14630843               14631777.673...
1b29               28192750               28194305.428...
1b30               54400028               54401475.618...
1b31              105097565              105100230.676...
1b32              203280221              203284081.999...
1b33              393615806              393619392.424...
1b34              762939111              762944445.930...
1b35             1480206279             1480216942.828...
1b36             2874398515             2874412059.223...
1b37             5586502348             5586518342.979...
1b38            10866266172            10866289002.503...
1b39            21151907950            21151933690.119...
1b40            41203088796            41203130440.933...
1b41            80316571436            80316641124.200...
1b42           156661034233           156661093268.208...
1b43           305761713237           305761828029.833...
1b44           597116381732           597116514592.781...
1b45          1166746786182          1166747049036.070...
1b46          2280998753949          2280998920877.337...
1b47          4461632979717          4461633199431.955...
1b48          8731188863470          8731189527167.853...
1b49         17094432576778         17094433493806.068...
1b50         33483379603407         33483380671829.765...
1b51         65612899915304         65612901724624.253...
1b52        128625503610475        128625505067379.811...
1b53        252252704148404        252252706016217.455...
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .