10
$\begingroup$

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.

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

4 Answers 4

5

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)}$

4

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.

1

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.

0

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$.