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

  • 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 '17 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 '17 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 '17 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 '17 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 '17 at 18:28

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

  • $\begingroup$ So I did base teen instead of base e. dad gum thanks $\endgroup$ Nov 13 '17 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 '17 at 13:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.