0
$\begingroup$

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)$.

$\endgroup$
9
  • 1
    $\begingroup$ Doubling the formula is not correct, you aren’t counting anything twice or half as many times, the formula gives an approximation regardless of how you are counting... $\endgroup$
    – abiessu
    Nov 13, 2017 at 18:08
  • 1
    $\begingroup$ A minor point: primes are primes no matter the base. Just mentioning this because I wasn't sure why you mentioned the numbers were represented in binary. You might be interested to know that it's not uncommon to represent big numbers on a computer in base $2^{16}$. $\endgroup$ Nov 13, 2017 at 18:11
  • 1
    $\begingroup$ " twice the number of primes in the range" you think there are even primes in that range? $\endgroup$
    – fleablood
    Nov 13, 2017 at 18:12
  • $\begingroup$ but there are no even primes in the range thus taking out the even ones would make there be more primes found in my program $\endgroup$ Nov 13, 2017 at 18:13
  • 1
    $\begingroup$ @tilper It looks like they are using it as an estimate of the probability of finding a prime, and they are conditioning it on the space of odd numbers. $\endgroup$ Nov 13, 2017 at 18:28

1 Answer 1

3
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ So I did base teen instead of base e. dad gum thanks $\endgroup$ Nov 13, 2017 at 18:42
  • $\begingroup$ the log symbol when we are talking cross discipline is somewhat ambiguous in fact when I initially did this calculation I assumed that it was $\log_2$ then in the middle I remember that for most "people" the $\log_{10}$ however I forgot in my ramblings that for number theorists its $\log_e$ :) $\endgroup$ Nov 14, 2017 at 13:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .