Associated Topics || Dr. Math Home || Search Dr. Math

### The Prime Number Theorem

```Date: 05/26/2008 at 21:20:54
From: Benjamin
Subject: the prime number theorem

Which one of the following formulas is true?  They are both given, one
after the other, in the book "Gamma" by Julian Havill.  Obviously both
cannot be true.

Let pi(x) be the number of primes below x.  Then

1. pi(x) - pi(sqrt(x)) + 1 = [prod over primes p, p<=x of (1-1/p)]x

or

2. pi(x) = same right hand side as above.

The second formula is used to derive a form of the prime number
theorem, i.e.

pi(x) = 2x e^gamma/ln(x)

Does it simply neglect pi(sqrt(x)) compared to pi(x)?

```

```
Date: 05/27/2008 at 00:27:56
From: Doctor Jordan
Subject: Re: the prime number theorem

Hi Benjamin,

We will use f(x) ~ g(x) to mean f(x)/g(x) goes to 1 as x goes to
infinity.  For example,

x^2 + x ~ x^2

since

x^2    x         1
--- + --- = 1 + ---
x^2   x^2        x

goes to 1 as x goes to infinity.

In particular this example shows us that two functions being
asymptotic (that is how we say ~) does not mean they are equal, since
of course x^2 + x is not equal to x^2.

The prime number theorem tells us that pi(x) ~ x/ln(x).

I will show that pi(x) - pi(sqrt(x)) also is asymptotic to x/ln(x).

pi(x) - pi(sqrt(x))    pi(x)    pi(sqrt(x)) * ln(x)
------------------- = ------- - -------------------
x/ln(x)         x/ln(x)            x

But pi(sqrt(x)) is certainly <= sqrt(x), since the number of primes <=
x is upper bounded by x itself.

Thus

pi(sqrt(x)) * ln(x)    sqrt(x) * ln(x)
------------------- <= ---------------
x                    x

Multiplying the right side by sqrt(x)/sqrt(x) gives

ln(x)
------
sqrt(x)

which goes to 0 as x goes to infinity, by L'Hospital's rule.

Therefore

pi(x) - pi(sqrt(x))
-------------------
x/ln(x)

goes to 1 as x goes to infinity, which shows that pi(x) - pi(sqrt(x))
is asymptotic to x/ln(x).

Therefore pi(x) is asymptotic to x/ln(x) and so is
pi(x) - pi(sqrt(x)).

- Doctor Jordan, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search