Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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))$. –  Douglas B. Staple Jun 6 '13 at 18:45
    
@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? –  JMCF125 Jun 6 '13 at 20:07
1  
$[x,y) = [x,y[$. I believe the later is older; the former is much more common in the fields I've worked in. –  Douglas B. Staple Jun 7 '13 at 13:27
1  
Also, elementary-number-theory would be a very appropriate tag for this question. –  Douglas B. Staple Jun 7 '13 at 13:32

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
1  
I'll make some more research on this and then mark this answer as accepted. Thank you for such a complete answer. –  JMCF125 Jun 8 '13 at 21:31
    
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. –  JMCF125 Jun 10 '13 at 15:40
1  
@JMCF125 You're welcome. I'm happy that you followed up so thoroughly on it. –  Douglas B. Staple Jun 10 '13 at 15:53

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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