# What is the growth rate of the sum of powers of distinct primes closest to a given a integer?

Let $$n$$ be a positive integer, and $$2 = p_1 < p_2 < \dots < p_m \le n$$ be the sequence of all primes less than or equal to $$n$$.

For each index $$j$$ let $$p_j^{e_j}$$ be the largest power of $$p_j$$ still less than or equal to $$n$$. Define

$$S_n = p_1^{e_1} + p_2^{e_2} + \dots + p_{m}^{e_m}$$

to be the sum of these prime powers. What is the growth rate of this series $$S_n$$?

We can get an upper bound of

$$S_n \le nm \sim \frac{n^2}{\ln n}$$

by the prime number theorem, and a lower bound of

$$S_n \ge \lfloor n/p_1\rfloor + \lfloor n/p_2\rfloor + \dots + \lfloor n/p_m\rfloor \sim n\ln \ln n$$

using the fact that each term $$p_j^{e_j}$$ is within a factor of $$p_j$$ of $$n$$ and asymptotics for the sum of the reciprocals of the primes.

However, there's still some gap between these two bounds. Is the precise asymptotic growth rate of $$S_n$$ known?

• If you just pick the primes bigger than n/2, that sum gets you close to the upper bound. You can improve upon this by taking the sum of all primes bigger than square root of n to get close to optimal. There will still be uncertainty of size sqrt(n)lnln n/in n, unless you do some hard work. Gerhard "Like Some Really Serious Arithmetic" Paseman, 2020.08.10. Aug 10, 2020 at 19:41
• Perhaps one can try to figure out the index $j$ that maximizes the quantity $n-p_{j}^{e_{j}}$ to refine the aforementioned bounds. Aug 10, 2020 at 19:48
• Also, the quantities $\delta_{j}:=n-p_{j}^{e_{j}}$ must be all different, so you can get this way a new upper bound $nm-m(m-1)/2$. Aug 10, 2020 at 19:53
• Would this be related to Sylvester Schur theorem? Gerhard "Is Really Interested In Motivation" Paseman, 2020.08.10. Aug 10, 2020 at 20:20

A better lower bound is $$S(n)$$, the sum of all primes below $$n$$, and this lower bound makes a good asymptotic value. One can tweak this by observing that for every term corresponding to a prime less than $$\sqrt{n}$$ that term is at least $$n^{2/3}$$, so a tighter lower bound like $$S(n) - S(\sqrt{n}) + n^{7/6}/\log n$$ is available. Since $$S(n)$$ is like $$O(n^2/\log n)$$, one wonders how good an asymptotic is desired.

Gerhard "Wonders What This Is For" Paseman, 2020.08.10.

• As observed in another comment thread, we have S(n) + O(n^{3/2}/\log n) as an upper bound, so there is not much room for improvement. Gerhard "Unless The Application Needs It?" Paseman, 2020.08.10. Aug 10, 2020 at 22:17

Only a partial answer for now. Denote by $$M$$ the quantity $$\max\{n-p_{j}^{e_{j}}\}$$. Then $$nm-m(m-1)/2\geq S_{n}\geq nm-M-(M-1)-(M-2)-\cdots\geq nm-mM+m(m-1)/2$$. So determining $$M$$ would get us closer to the real order of growth of $$S_{n}$$.

Edited after Gerhard's contributions: let now $$x_n$$ be the solution of $$x_n=\frac{\log n}{\log x_n}$$. Then a lower bound for $$S_{n}$$ is $$\sum_{p\leq x_{n}}p^{\lfloor\frac{\log n}{\log p}\rfloor}+S(n)-S(x_n)$$ but this must be difficult to estimate.

• Unfortunately M is almost n minus sqrt(n), so this will lead to a poor estimate. Better to just take sum of primes below n. Gerhard "But Many Have Same Parity" Paseman, 2020.08.10. Aug 10, 2020 at 21:13
• Kinda curiously one has $S_{100}=1230=\pi(100^2)+1$. So maybe one can expect to have $S_{n}\sim \frac{n^{2}}{2\log n}$. Aug 10, 2020 at 21:42
• Indeed, one has that already using S(n) as a lower bound (as in my posted answer), and the poster's sum differs from that by less than n^3/2. Gerhard "The Powers Aren't Very Powerful" Paseman, 2020.08.10. Aug 10, 2020 at 21:53
• Also $x_n$ is the "square root for tetration" of $n$, so this might provide a "natural" explanation for the factor $1/2$ as "tetration power" (which I admit is extremely speculative). Aug 10, 2020 at 22:02
• For $n=100$, the error between $S_n$ and my lower bound is around $\frac{4}{3}\sqrt{n}\log n$, which is, up the implied constant, the error term for the PNT under RH. Aug 10, 2020 at 22:17