The sum of the first $$n$$ primes less than $$\sqrt{n}$$:

On the MathOverflow, I recently came across the following theorem:

$$S(n) = \sum_{p \leq \sqrt{n}} p$$

$$S(n) \sim \pi(n)$$

although the proof of this theorem is rather elementary, I don’t think anybody would have expected this result unless they first came across Mertens’ three theorems.

Even then however, this result is quite unexpected.

Proof:

If we let $$X_p = 1$$ if $$p \in \mathbb{P}$$ and $$X_p = 0$$ otherwise, then we have:

$$\pi(n) \sim \sum_{p \leq n} X_p$$

and we also have:

$$\lfloor \sqrt{n} \rfloor \cdot \pi(\sqrt{n}) = \sum_{p \leq \sqrt{n}} \lfloor \sqrt{n} \rfloor \cdot X_p$$

$$\sum_{p \leq \sqrt{n}} \pi(p) = \sum_{p \leq \lfloor \sqrt{n} \rfloor - 1} (\lfloor \sqrt{n} \rfloor - 1 - (p-1)) \cdot X_p = \sum_{p \leq \lfloor \sqrt{n} \rfloor - 1} (\lfloor \sqrt{n} \rfloor - p) \cdot X_p$$

Given the definition of $$S(n)$$ we have:

$$S(n) = \lfloor \sqrt{n} \rfloor \cdot \pi(\sqrt{n}) - \sum_{p \leq \sqrt{n}} \pi(p)$$

Now, if we use the error term of the Prime Number Theorem we have:

$$\lvert \pi(N) - \frac{N}{\ln N} \rvert = \mathcal{O}\big(\frac{N}{(\ln N)^2}\big)$$

and therefore:

$$S(n) = \lfloor \sqrt{n} \rfloor \cdot \frac{\sqrt{n}}{\ln \sqrt{n}} - \sum_{k=2}^{\lfloor \sqrt{n} \rfloor - 1} \frac{k}{\ln k} + \mathcal{O}\big(\frac{n}{(\ln \sqrt{n})^2}\big)$$

Meanwhile, using integration by parts we find:

$$\int_{2}^{\sqrt{n}} \frac{x}{\ln x} dx \approx \frac{n}{\ln n} - \int_{2}^{\sqrt{n}} \frac{x^2}{(\ln x)^2} dx \leq \frac{n}{\ln n} -4 \cdot \frac{n}{(\ln n)^2} = \frac{n}{\ln n} + \mathcal{O}\big(\frac{n}{(\ln n)^2}\big)$$

so (8) simplifies to:

$$S(n) \sim \frac{n}{\ln n} + \mathcal{O}\big(\frac{n}{(\ln n)^2}\big)$$

QED.