[Math] Prime numbers in binary.

prime numbers

So I am currently writing a computer program which among other things computes huge binary prime numbers. I am testing it on 16 digit numbers. So here is my question. So I generate 100 random odd numbers (aka a 16 digit string of binary numbers that begin and end with one). Then using the fact that
$$
\pi(x) \approx \frac{x}{\log x}
$$
Then obviously a rough approximation of the number of primes I will generate find in this range with 100 random guess is
$$
2 * 100\frac{\left(\frac{2^{16}}{\log{2^{16}}}-\frac{2^{15}-1}{\log(2^{15}-1)} \right)}{2^{16}-2^{15}+1}
$$
since it would be twice the number of primes in the range $[2^{15}-1,2^{16}]$ since I am only considering odd numbers. However this gives me about ~38 primes and my code is generating consistently 16-25. So is my math wrong or is this approximation not good for this (relatively) small values of $\pi(x)$.

Best Answer

In case the exact number helps, Mathematica can compute PrimePi[2^16] - PrimePi[2^15 - 1] to be $3030$. Choosing one-hundred odd integers uniformly at random from $[2^{15},2^{16}]$, the expected number of primes among them is $20200/10923\approx 18.4931$.

Calculating the approximation with the prime number theorem, I get approximately $16.8315$. The logarithms are supposed to be base-$e$: if I redo the calculation with base-$10$ logarithms, I get approximately $38.7559$.

Related Question