Take the 2-minute tour ×
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.

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|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
2  
@AsafKaragila You are wrong. If $p$ is the $n$th prime, then $\frac p{\ln p}\approx n$. With $n=2^{31}$, this holds for $p\approx 5.5\cdot 10^{10}$. –  Hagen von Eitzen Nov 19 '12 at 17:29
    
@user1551: Good thing we cannot store numbers as strings, and use bignum libraries! –  Asaf Karagila Nov 19 '12 at 17:30
    
@Hagen: I stand corrected, that makes much more sense than what I said! :-) –  Asaf Karagila Nov 19 '12 at 17:32
    
@AsafKaragila Exactly how it would be stored, assuming it is within a reasonable range; ie: I have enough memory on my computer. –  awashburn Nov 19 '12 at 17:32
show 7 more comments

2 Answers 2

up vote 10 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|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. –  awashburn 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
add comment

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|improve this answer
add comment

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.