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$ – Gerhard Paseman Aug 10 '20 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$ – Sylvain JULIEN Aug 10 '20 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$ – Sylvain JULIEN Aug 10 '20 at 19:53
  • $\begingroup$ Would this be related to Sylvester Schur theorem? Gerhard "Is Really Interested In Motivation" Paseman, 2020.08.10. $\endgroup$ – Gerhard Paseman Aug 10 '20 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.

  • $\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$ – Gerhard Paseman Aug 10 '20 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$ – Gerhard Paseman Aug 10 '20 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$ – Sylvain JULIEN Aug 10 '20 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$ – Gerhard Paseman Aug 10 '20 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$ – Sylvain JULIEN Aug 10 '20 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$ – Sylvain JULIEN Aug 10 '20 at 22:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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