Let $ p_i $ denote the $ i $-th prime number. Let $ n = \lfloor\alpha^{2015}\rfloor $, where $ \alpha $ is a positive real number such that $ 2 < \alpha < 2.7 $. Prove that $$ \displaystyle\sum_{2 \le p_i \le p_j \le n}\frac{1}{p_ip_j} < 2017 $$
Problem
Source: Junior Olympiad of Malaysia Shortlist 2015 N6
Tags: number theory
14.11.2016 19:37
Up! Up!
02.11.2017 15:44
$bumpbump$
02.11.2017 17:50
That definition for $n$ is weird, and problems like this definitely shouldn't be used in olympiads... Anyway, let us just fix $n = \lfloor 2.7^{2015}\rfloor < e^{2015}$. Throughout this post, $p$ will always denote a prime. Overkill: It's possible to overkill this by just noting that the LHS is equal to $\frac{1}{2}\left(\left(\sum_{p\leq n} \frac{1}{p_i}\right)^2 + \sum_{p\leq n} \frac{1}{p^2}\right)$ and using the bounds $ \sum_{p\leq n} \frac{1}{p_i} <\ln\ln n + 1$ and $\sum_{p\leq n} \frac{1}{p_i^2} < 1$. Using only $\sum_{k=1}^n \frac{1}{k} \leq 1 + \ln n$: Note that any positive integer can be written in the form $spq$ with $s\in S=\{1,2,4,8,9,16\}$ and $p,q$ distinct primes in at most one way. With this, we obtain the estimate $$\frac{295}{144} \sum_{2\leq p_i\leq p_j\leq n}\frac{1}{p_ip_j} = \sum_{s\in S}\frac{1}{s}\left( \sum_{p<n} \frac{1}{p^2} + \sum_{2\leq p_i< p_j\leq n}\frac{1}{p_ip_j} \right)$$$$ < \sum_{s\in S}\frac{1}{s}\sum_p \frac{1}{p^2} + \sum_{k=1}^{16n^2} \frac{1}{k} < \frac{295}{144} + \ln (16n^2) + 1$$$$ < 3 + 4034 + 1 = 4038 < \frac{295\cdot 2017}{144}.$$