It is easily be proved by the famous thoerem: $\pi (x)\sim\frac{x}{\ln x+c}$ And I also have an elemetry proof of it(I'll post it tommorrow). I wonder that if there's an elemetry proof of the above theorem. And I also don't know if we can prove with elementry method the following problem: $\frac{\pi(x)}{x^r}-->\infty,r<1$

Hawk Tiger wrote: And I also have an elemetry proof of it(I'll post it tommorrow). I think, your days are very long!

It suffices to use Chebyshev's theorem (namely that $ \pi(x) \cdot \log(x) \geq c \cdot x$) instead of the much stronger prime number theorem.

That's still not elementary... I am curious for Hawk Tiger's elementary proof.

Sorry but you really should define your "elementary". You have now neglected a big amount of solutions for not being "elementary"...

Calm down... Maybe it is just because I am too sleepy to see the easy proof of the "Chebyshev's theorem" you seem to have. If you have a proof of it without prerequisites, then it is of course ok. (and then it is appreciated if you post the proof too, for the people not knowing the proof, like me). As long as you use theorems I have not ever seen a proof of (like this one, of course everyone knows the fact) I will find your proof nonelementary. Yes, elementaryness is a little subjective. I'm open to more formal definitions.

Sorry for being a bit harsh... See http://planetmath.org/?op=getobj&from=objects&id=8545 for an elementary proof. I totally agree that this may be too long or too much work et cetera. My comment was not specially on this problem, but was meant more general. Please don't call any method that aren't part of some special courses nonelementary. I see a very important part of any number theory book (expecially PEN) to learn new theorems and methods, not only applying old ones to solve single problems. Thus I consider it very important to teach new techniques. And after you got used to something, you are more likely to call it elementary.

Oh but I would never call a 'method' nonelementary. I'm all for learning new techniques, methods and tricks. Please point me out if I ever spoke against that, because then I probably misunderstood what it was about. What I am against is that sometimes, people use (often relatively deep) theorems - without proof - that nearly trivialize the problem (like you both did here). Of course this follows from Chebyshev and from the Prime Number Theorem. The reason this problem is in the book is because there presumably exists some brilliant inductive construction of the pairs without knowledge on prime distribution, not to be a standard application of some prime distribution theorem. In the same way one can claim to have verified in Maple that 1280000401 is composite. Of course that solves the problem. But this doesn't contribute any ideas either. I agree there is not always clear wether one is expected to find a competition-style solution (no theorems without proof and by hand) or just any solution (research style), this seems to depend from problem to problem. I will try to take care of this in the next release (which is greatly slowed down by moving to MathLinks).

I try to give as elementary proofs $ E$ often as possible, but there are cases where it is better to give an nonelementary proof $ N$: - the result obviously is of nonelementary style. - $ E$ is not essentially different from an "elementarisation" of $ N$; then I prefer writting down $ N$ and explaing/adding all the missing steps: otherwise the solution would pop out of nothing, and this way the reader can learn new methods and theorems. - $ E$ relies on difficult but elementary and known theorems (like here); then one (at least I) doesn't always want to add a proof (even if it is elementary); one really good example is Zigmondy's theorem... By the way, I think this problem can be done more directly, but for the "learning effect", e.g. how one could do it with a bit more theorems known, the non- or half-elementary solutions are ok.

You can easily derive it from the fact that the series of inverse primes diverges and the series of inverse squares converges. Both claims are "reasonably elementary" .

fedja wrote: You can easily derive it from the fact that the series of inverse primes diverges and the series of inverse squares converges. Both claims are "reasonably elementary" . we have two formulas for that. i am going to introduce the full solution of fedja we know that \[\sum \frac{1}{i^2}=\frac{\pi^2}{6}\]and also,\[ \sum \frac{1}{P_i}=\infty \]\text{where $P_i$ is the $i_{th}$ prime number} now our idea is to use contradiction, consider that the most prime numbers that could occur between two consecutive squares is $\leq 999$ then we list all consecutive squares: \[\begin{array}{cccc} (1^2,2^2)\\(2^2,3^2)\\ \cdots \\ \cdots \end{array}\] so hear we can give an upper bound for the sum of inverse of primes in interval $(t^2,(t+1)^2)$ and that is \[\sum_{t^2 \leq P_i<(t+1)^2} \frac{1}{P_i} \leq \frac{999}{t^2} \thinspace \thinspace \thinspace \textbf{(1)}\]so for all primes we have : \[ \sum_{i=1}^{\infty} \frac{1}{P_i} \leq 999\sum_{i=1}^{\infty} \frac{1}{t_i^2} \thinspace \thinspace \thinspace \textbf{(2)}\]but from the formulas that i have mentioned earlier about the sum of inverses it is obviously wrong because the left hand side of $(2)$ is equal to $\infty$ but the right hand side is less than $2*999$. hence,contradiction..