11
$\begingroup$

In computer science an array is indexed by an integer (int). Unlike in mathematics, the computer science integer (int) has a finite range defined by the length of it's fixed binary representation.

In most modern higher level languages the maximum value of an integer is 2^31 - 1 (2147483647). I would like to create an array of sequential primes in a computer program I intend to write.

Example:

  list[0] =  2;
  list[1] =  3;
  list[2] =  5;  
  list[3] =  7;  
  list[4] = 11;  etc...

However, an array is indexed by an int so I can only have 2,147,483,647 entries in the array. Because of this I would like to know what the largest prime I could place in the array of sequential prime entries.

What value would be placed in list[2147483647] = x; What is the 2,147,483,647th prime number?

I'm not asking anyone in particular to calculate primes up to that iteration. I'm wondering how I might go about calculating it or find a place where it has already been precomputed. I know Wolfram has some precomputed primes but I couldn't find the correct prime tables.

EDIT: I ask this question because I come from a computing background, not mathematics and I have difficulty estimating the size of the 2,147,483,647th prime number. Rather then the exact value, a rough value will suffice. I just need to know how roughly large this prime is.

  1. If represented in binary, roughly how may bits would the 2,147,483,647th prime contain?

  2. If represented in decimal, roughly how may digits would the 2,147,483,647th prime contain?

$\endgroup$
7
  • 3
    $\begingroup$ You can compute it in Mathematica, simply Prime[2147483647] yields 50685770143. For some interesting subtleties concerning Prime I recommend reading this question : mathematica.stackexchange.com/questions/3327/… $\endgroup$
    – Artes
    Commented Nov 19, 2012 at 17:28
  • $\begingroup$ @awashburn: yes, that prime is around 5.5E10, but Artes gave the exact value. It has 11 decimal digits or 36 bits $\endgroup$ Commented Nov 19, 2012 at 17:38
  • $\begingroup$ @awashburn You can compute Prime[2147483647] in Wolfram|Alpha as well, since it relies on Mathematica. $\endgroup$
    – Artes
    Commented Nov 19, 2012 at 17:55
  • $\begingroup$ @Artes Is Mathematica consulting a lookup table; or actually calculating the first N primes in order to return Prime[N]? $\endgroup$ Commented Nov 20, 2012 at 13:21
  • 2
    $\begingroup$ I object to the notion that computer science integers necessarily have finite range. Programming integers tend to have finite range (although unlimited representations are standard in e.g. Python and Haskell), but computer science is not programming :) $\endgroup$ Commented Feb 17, 2013 at 23:57

2 Answers 2

15
$\begingroup$

I'm not quite sure why you need to know what the $2147483647$-th prime number is, but I'm going to guess it's so you know what data type to store the elements of the array in.

In that case, you only need an approximate value. The Prime Number Theorem tells us that

$$\pi(n)\approx\frac{n}{\log(n)}$$

where $\pi(n)$ is the number of prime numbers less than $n$. So we are looking for $n$ with $\pi(n)\ge2147483647$ (then there are at least $2147483647$ primes less than $n$, so in particular the first $2147483647$ primes are all smaller than $n$, and can be stored in variables of size $n$).

Let's just ignore the $\approx$ sign and treat it as an equality. This means we might accidentally get a value that's too small, but let's not worry about that.

So we want

$$\pi(n)=\frac{n}{\log(n)}=2147483647$$

Wolfram|Alpha gives an answer of $5.303\times 10^{10}$ for $n$.

Now $\log_2(5.03\times 10^{10})\approx 35.5$, so you'd need 36 bits to store that number.

$\log_{10}(5.03\times10^{10})\approx 10.7$, so you'd need $11$ digits to represent the $2147483647$-th prime number in decimal.

$\endgroup$
2
  • $\begingroup$ This was exceeding helpful. I hope one day to be better versed in mathematics so I could manage these calculations on my own. $\endgroup$ Commented Nov 19, 2012 at 17:40
  • 6
    $\begingroup$ The approximation of $\pi(x)$ is good asymptotically (prime number theorem) but for any finite number it may be far from the correct value which is 50685770143 for 2147483647 th prime. A better approximation is given by the Riemann prime counting function. $\endgroup$
    – Artes
    Commented Nov 19, 2012 at 17:47
14
$\begingroup$

Just so we have an answer: As Artes has shown, the exact prime is $50685770143$. This has $11$ decimal digits. In binary, it is $101111001101000110110111100110011111_2$, which has $36$ bits.

$\endgroup$

You must log in to answer this question.

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