0

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

Riemann-bitcoin.
  • 441
  • 2
  • 15
  • 1
    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... – abiessu Nov 13 '17 at 18:08
  • 1
    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}$. – Kyle Miller Nov 13 '17 at 18:11
  • 1
    " twice the number of primes in the range" you think there are even primes in that range? – fleablood Nov 13 '17 at 18:12
  • 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 – Riemann-bitcoin. Nov 13 '17 at 18:13
  • edited for clarity – Riemann-bitcoin. Nov 13 '17 at 18:19
  • $x / \log x$ gives you an approximation of the number of primes in the interval $[2, x]$. Why do you think the formula will change if you exclude even numbers? The only even prime is $2$, so the actual count decreases by $1$, which doesn't change the approximation. –  Nov 13 '17 at 18:25
  • but since it is the number of primes this range since I am only considering odd number then when calculating the chance I multiply by 2 – Riemann-bitcoin. Nov 13 '17 at 18:27
  • 1
    @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. – Kyle Miller Nov 13 '17 at 18:28
  • @KyleMiller, I see now. The way the post is written it sounds like OP is doubling the prime-counting formula $(x / \log x)$, but upon inspecting the formula (incorrectly labeled "an approximation of the number of primes"), it seems OP is actually calculating a probability. Also, the original version of the post had a formula that wasn't a probability, but rather, was the actual number of primes. Perhaps the label didn't get updated with the formula. Thanks for the clarification. –  Nov 13 '17 at 18:34

1 Answers1

3

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

Kyle Miller
  • 19,353
  • So I did base teen instead of base e. dad gum thanks – Riemann-bitcoin. Nov 13 '17 at 18:42
  • 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$ :) – Riemann-bitcoin. Nov 14 '17 at 13:30