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.

Problem 1. Prove that there exists $n\in\mathbb{N}$ such that in interval $(n^2, \ (n+1)^2)$ there are at least $1000$ prime numbers.

Problem 2. Let $s_n=p_1+p_2+...+p_n$ where $p_i$ is the $i$-th prime number. Prove that for every $n$, there exists $k\in\mathbb{N}$ such that $s_n<k^2<s_{n+1}$.

I've found these two a while ago and they interested me. But don't have any ideas.

share|improve this question

4 Answers 4

up vote 5 down vote accepted

Problem 2: For any positive real $x$, there is a square between $x$ and $x+2\sqrt{x}+2$. Therefore it will suffice to show that $p_{n+1}\geq 2\sqrt{s_n}+2$. We have $s_{n}\leq np_n$ and $p_{n+1}\geq p_n+2$, so we just need to show $p_n\geq 2\sqrt{np_n}$, i.e., $p_n\geq 4n$. That this holds for all sufficiently large $n$ follows either from a Chebyshev-type estimate $\pi(x)\asymp\frac{x}{\log(x)}\,$ (we could also use PNT, but we don't need the full strength of this theorem), or by noting that fewer than $\frac{1}{4}$ of the residue classes mod $210=2\cdot3\cdot5\cdot7$ are coprime to $210$. We can check that statement by hand for small $n$.

There have already been a couple of answers, but here is my take on problem 1: Suppose the statement is false. It follows that $\pi(x)\leq 1000\sqrt{x}$ for all $x$. This contradicts Chebyshev's estimate $\pi(x)\asymp \frac{x}{\log(x)}$

share|improve this answer

For the first one, you can prove that there is a positive integer $n$ such that $\pi((n+1)^2 - 1) - \pi(n^{2}) \geqslant 1000$, where $\pi$ is the prime counting function, using the Prime Number Theorem.

For the second one, I believe Bertrand's Postulate may be useful.

share|improve this answer

Solution to the first:

By inspection of the primes, pick $n = 8715$. Note that $n^2 = 75951225 < 75951233$, and $(n+1)^2 = 75968656 > 75968723$.

Now $75951233$ and $75968723$ are primes, with $\ge 1000$ primes between them so we're done. [1]


[1] The $4446857$th prime is $75951233$ and the $4447859$th prime is $75968723$ (source: http://primes.utm.edu/nthprime/index.php). Further, $4447859 - 4446857 = 1002$.

Exercise: Show that $n = 8715$ is the minimum $n$ satisfying the claim.

share|improve this answer

Here's my attempt on the first part of the question, I'm not sure how valid it is, though; so I'd appreciate feedback/corrections:

It is known that: $\pi(n)\sim\frac{n}{\ln{n}}$. Where $\pi(n)$ is the prime counting function on $n$ (i.e. the number of primes less than or equal to $n$).

Therefore, we are looking to show that there exists some $n$ such that:

$$\frac{(n+1)^{2}}{2\ln{(n+1)}}-\frac{n^{2}}{2\ln{n}}\geqslant1000$$

Let us call $\pi_{d}(n)=\frac{(n+1)^{2}}{2\ln{(n+1)}}-\frac{n^{2}}{2\ln{n}}$. Therefore, we have:

$$\frac{d\pi_{d}}{dn}=\left(\frac{n}{2\left(\ln{n}\right)^{2}}+\frac{n+1}{\ln{(n+1)}}\right)-\left(\frac{n}{\ln{n}}+\frac{n+1}{2\left(\ln{(n+1)}\right)^{2}}\right)$$

Therefore $\frac{d\pi_{d}}{dn}\gt0$, $\forall n\gt0$. Therefore, as $\pi_{d}(n)$ is monotonically increasing: $\exists n:\pi((n+1)^{2})-\pi(n^{2})\geqslant1000$.

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.