1
$\begingroup$

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.

  • 0
    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.2010-11-19
  • 3
    How close do the two quantities have to be to be "almost the same"? What sort of error margin is acceptable?2010-11-19

1 Answers 1

2

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.