From Example Problems
Jump to: navigation, search

Prove that \pi (x) (the number of primes less than x) is bounded below by \log \log x.

Let p_{n}\, be the n^{{th}} prime. Let q=2\cdot 3\cdot 5\cdot \cdot \cdot p_{n}+1.

By the proof of NT1, p_{{n+1}}\leq q.

Suppose that p_{n}<2^{{2^{n}}} for n=1,2,...,N. It is true for n=1. The last result gives

p_{{N+1}}\leq p_{1}p_{2}...p_{N}+1<2^{{2+4+...+2^{N}}}+1<2^{{2^{{N+1}}}}

which proves it inductively for all n.

Suppose n\geq 4. Let x be such that

e^{{e^{{n-1}}}}<x\leq e^{{e^{n}}}.



it is true that


And so

\pi (x)\geq \pi (e^{{e^{{n-1}}}})\geq \pi (2^{{2^{n}}})\geq n\,

Since \log \log x\leq n, it is true that

\pi (x)\geq \log \log x,x\geq 2

Main Page : Number Theory