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.

I have an interval $[2,t]$ containing some number of primes. I now want to divide this interval into two intervals $a=[2,m]$ and $b=]m,t]$ such that the number of primes in $a$ and $b$ is almost the same.

I am aware of the approximation $\pi(t)=\frac{t}{2\ln(t)}$, but can not seem to get any good and usable result out of this.

This is for a computer implementation, so avoiding Lambert functions and likewise functions would be much appreciated.

share|improve this question
    
I don't understand the requirement for avoiding the Lambert function; there are excellent subroutines available for computing it, and the algorithm for it is pretty straightforward if your environment of choice does not support it. –  J. M. Nov 19 '10 at 14:23
3  
How close do the two quantities have to be to be "almost the same"? What sort of error margin is acceptable? –  Niel de Beaudrap Nov 19 '10 at 14:38
add comment

1 Answer 1

up vote 2 down vote accepted

The approximation $\pi(x) \sim \frac{x}{\ln x}$ given by the prime number theorem tells you there are about $\frac{t}{\ln t}$ primes in $[2, t]$. Now, the PNT also tells you that the $n^{th}$ prime $p_n$ behaves asymptotically like $p_n \sim n \ln n$. We want $n \sim \frac{t}{2 \ln t}$, hence

$$m \sim \frac{t}{2 \ln t} \left( \ln t - \ln 2 - \ln \ln t \right).$$

What this tells you is that for reasonably large values of $t$ (say a hundred digits) the approximation $m \sim \frac{t}{2 \ln t}$ should work quite well. For small values of $t$ you are probably better off using the sieve of Erathosthenes to explicitly count primes. You shouldn't really trust the other two terms anyway because the two approximations I gave above are only compatible up to ignoring them.

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.