L567 wrote: A natural number $n$ is given. Prove that $$\sum_{n \le p \le n^2} \frac{1}{p} < 2$$where the sum is across all primes $p$ in the range $[n, n^2]$ It suffices to show to $\pi(N^2)<2p_N+\pi(N)$ where $p_N$ is the smallest prime larger then $N$ which is true by PNT.

Sprites wrote: It suffices to show to $\pi(N^2)<2p_N+\pi(N)$ where $p_N$ is the smallest prime larger then $N$ which is true by PNT. Unfortunately, this is not at all true! Note that by the PNT we have $RHS \sim 2N\log(N)$ while $LHS \sim \frac{N^2}{2\log N}$ which is much bigger when $N$ becomes large.

While the attempt in #2 to use analytic machinery fails, there is of course a way to estimate this analytically and as explained in the similar problem here, the LHS converges to $\log(2)$ as $n \to \infty$ (which is much smaller than $2$), so the claim is at least true for all large $n$. However, proving the claim for all $n$ leaves one with annoying bit of estimating the error terms in the asymptotic. Using analytic machinery really is not the right way to approach this nice problem, which in fact is very similar to a classic, e.g. from German TSTST 2003. The key observation of the short proof is to note that if $p_1,\dots,p_k$ are all the primes in the interval $[n,n^2)$, then any number in this interval is divisible by at most one of the $p_i$. But the number of multiples of $p_i$ in the interval is certainly more than $\frac{N^2-N}{p_i}-1$. Hence \[N^2-N >\sum_{i=1}^k \left(\frac{N^2-N}{p_i}-1\right)\]and hence $\sum_{i=1}^k \frac{1}{p_i}<1+\frac{k}{N^2-N} \le 2$ as desired. (As shown by the corresponding problem in grade 10, one can relax the condition of being prime slightly. This probably also makes the problem easier since it suggests what is the important part of the data.)

From AMSP Combinatorics 3: Consider the set $\{1, 2, 3, \cdots, n^2-1\}$. The expression $$\sum_{n \leq p \leq n^2} \left \lfloor \frac{n^2-1}p\right \rfloor$$denotes the number of multiples of some $p \in [n, n^2]$ in $\{1, 2, \cdots, n^2-1\}$. Notice that the set of multiples of every prime $p$ in this range are disjoint, because $pq > n^2$ otherwise. As a result, we have $$\sum_{n \leq p \leq n^2} \left \lfloor \frac{n^2-1}p\right \rfloor > \sum_{n \leq p \leq n^2} \left(\frac{n^2-1}p - 1\right).$$Thus, $$(n^2-1) \sum \frac 1p - (n^2-1) < n^2-1 \iff \frac 1p < 2,$$so we are done.