3
$\begingroup$

This is a question I have put to myself a long time ago, although only now am I posting it. The thing is, though there is an infinity of prime numbers, they become more and more scarce the further you go.

So back then, I decided to make an inefficient program (the inefficiency was not intended, I just wanted to do it quickly, I took more than 10 minutes to get the numbers below, and got them now from a sheet of paper, not the program) to count primes between bases of different numbers.

These are the numbers I got $($below the first numbers are the exponents of $x$, I used a logarithmic scale, in the first line $\forall \ (n$-- $n+1)$ means $ [b^n; b^n+1[$ $)$

---------0-1--2---3----4----5--6---7---8----9----10--11--12--13-----------------
base  2: |0| 2|  2|   2|   5| 7| 13| 23|  43|  75|137|255|464|
base  3: |1| 3| 13|  13|  31|76|198|520|1380|3741|
base 10: |4|21|143|1061|8363|

I made three histograms from this data (one for each base, with the respective logarithmic scales both on the $x$ and $y$ axes) and drew a line over them, that seemed like a linear function (you can try it yourselves, or if you prefer, insert these into some program like Excel, Geogebra, etc.).

My question is: are these lines really tending (as the base and/or as x grows) to linear or even any kind of function describable by a closed form expression?

$\endgroup$
4
  • 1
    $\begingroup$ PS. If you want to find on average $y$ primes in each interval, then you should check intervals of the form $[x,x+y\ln(x))$. $\endgroup$ Jun 6, 2013 at 18:45
  • $\begingroup$ @Douglas, I'll try it as soon as I find the program. BTW, why do you use ')' instead of '[' for an interval which doesn't include the last value? $\endgroup$
    – JMCF125
    Jun 6, 2013 at 20:07
  • 1
    $\begingroup$ $[x,y) = [x,y[$. I believe the later is older; the former is much more common in the fields I've worked in. $\endgroup$ Jun 7, 2013 at 13:27
  • 1
    $\begingroup$ Also, elementary-number-theory would be a very appropriate tag for this question. $\endgroup$ Jun 7, 2013 at 13:32

2 Answers 2

4
$\begingroup$

The prime number theorem is what you need. A rough statement is that if $\pi(x)$ is the number of primes $p \leq x$, then $$ \pi(x) \sim \frac{x}{\ln(x)} $$ Here "$\sim$" denotes "is asymptotically equal to".

A corollary of the prime number theorem is that, for $1\ll y\ll x$, then $\pi(x)-\pi(x-y) \sim y/\ln(x)$. So yes, the number of primes start to thin out for larger $x$; in fact, their density drops logarithmically.

To address your specific question, the PNT implies: \begin{align} \pi(b^{x+1}) - \pi(b^x) &\sim \frac{b^{x+1}}{\ln( b^{x+1} )} - \frac{b^x}{\ln( b^x )}, \end{align} where \begin{align} \frac{b^{x+1}}{\ln( b^{x+1} )} - \frac{b^x}{\ln( b^x )} &= \frac{b^{x+1}}{x+1\ln(b)} - \frac{b^x}{x\ln(b)}\\ &= \frac{b^{x+1}}{(x+1)\ln(b)} - \frac{b^x}{x\ln(b)}\\ &=\frac{b^x}{\ln(b)}\left( \frac{b}{x+1} - \frac{1}{x} \right)\\ &=\frac{b^x}{\ln(b)}\left( \frac{ bx-(x+1) }{x(x+1)} \right)\\ &=\frac{b^x}{\ln(b)}\left( \frac{ x(b-1)-1) }{x(x+1)} \right)\\ \end{align} For $x\gg 1$, we can neglect '$-1$' next to $x(b-1)$ in the numerator and $1$ next to $x$ in the denominator, so that: \begin{align} \frac{b^{x+1}}{\ln( b^{x+1} )} - \frac{b^x}{\ln( b^x )} &= \frac{b^x}{\ln(b)}\left( \frac{ x(b-1) }{x^2} \right)\\ &=\frac{b^x(b-1)}{x\ln(b)}, \end{align} so that $$ \pi(b^{x+1}) - \pi(b^x) \sim \frac{b^x(b-1)}{x\ln(b)}. $$ As I'm writing this, I see that this is exactly the same as the answer that @Charles gave.

$\endgroup$
3
  • 1
    $\begingroup$ I'll make some more research on this and then mark this answer as accepted. Thank you for such a complete answer. $\endgroup$
    – JMCF125
    Jun 8, 2013 at 21:31
  • $\begingroup$ So, directly answering my question, the described lines tend to linear as $x$ increases when the base is $e$; because in $\frac{b^x(b-1)}{x\ln(b)}$ the -1 becomes neglectable and $x \ln(e)=x$ and a division like that makes a linear function (in a logarithmic scale of base $b=e$). BTW, I also upvoted @Charles answer as he gave the same answer, I'll mark yours as accepted for a perfect explanation. And you still left me a bit to figure out, which I appreciate better than a direct answer. $\endgroup$
    – JMCF125
    Jun 10, 2013 at 15:40
  • 1
    $\begingroup$ @JMCF125 You're welcome. I'm happy that you followed up so thoroughly on it. $\endgroup$ Jun 10, 2013 at 15:53
2
$\begingroup$

Assuming $b\ge1$ there are $$ \sim\frac{b-1}{\log b}\cdot\frac{b^x}{x} $$ primes from $b^x$ to $b^{x+1}$ by the Prime Number Theorem.

$\endgroup$

You must log in to answer this question.

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