The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
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


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


  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.


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

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


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


  pi(x) - pi(sqrt(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)).

Does this answer your question?

- Doctor Jordan, The Math Forum 
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

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.