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?

  • 2
    $\begingroup$ 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. $\endgroup$ Aug 10, 2020 at 19:41
  • $\begingroup$ Perhaps one can try to figure out the index $j$ that maximizes the quantity $n-p_{j}^{e_{j}}$ to refine the aforementioned bounds. $\endgroup$ Aug 10, 2020 at 19:48
  • 1
    $\begingroup$ 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$. $\endgroup$ Aug 10, 2020 at 19:53
  • $\begingroup$ Would this be related to Sylvester Schur theorem? Gerhard "Is Really Interested In Motivation" Paseman, 2020.08.10. $\endgroup$ Aug 10, 2020 at 20:20

2 Answers 2


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.

  • $\begingroup$ 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. $\endgroup$ 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.

  • $\begingroup$ 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. $\endgroup$ Aug 10, 2020 at 21:13
  • $\begingroup$ 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}$. $\endgroup$ Aug 10, 2020 at 21:42
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 10, 2020 at 21:53
  • $\begingroup$ 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). $\endgroup$ Aug 10, 2020 at 22:02
  • $\begingroup$ 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. $\endgroup$ Aug 10, 2020 at 22:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.