Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
3  
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/… – Artes Nov 19 '12 at 17:28
    
@awashburn: yes, that prime is around 5.5E10, but Artes gave the exact value. It has 11 decimal digits or 36 bits – Ross Millikan Nov 19 '12 at 17:38
    
@awashburn You can compute Prime[2147483647] in Wolfram|Alpha as well, since it relies on Mathematica. – Artes Nov 19 '12 at 17:55
    
@Artes Is Mathematica consulting a lookup table; or actually calculating the first N primes in order to return Prime[N]? – Dan Neely Nov 20 '12 at 13:21
    
@DanNeely In reference.wolfram.com/mathematica/tutorial/… you can find e.g. a note on Number Theoretic Functions, it says Prime and PrimePi use sparse caching and sieving. For large n, the Lagarias-Miller-Odlyzko algorithm for PrimePi is used, based on asymptotic estimates of the density of primes, and is inverted to give Prime. – Artes Nov 20 '12 at 14:08
up vote 11 down vote accepted

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.

share|cite|improve this answer
    
This was exceeding helpful. I hope one day to be better versed in mathematics so I could manage these calculations on my own. – recursion.ninja Nov 19 '12 at 17:40
2  
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. – Artes Nov 19 '12 at 17:47

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.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.