2
$\begingroup$

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?

$\endgroup$
4
  • 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$ Commented 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$ Commented 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$ Commented 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$ Commented Aug 10, 2020 at 20:20

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
  • $\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$ Commented Aug 10, 2020 at 22:17
0
$\begingroup$

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.

$\endgroup$
7
  • $\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$ Commented 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$ Commented 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$ Commented 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$ Commented 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$ Commented Aug 10, 2020 at 22:17

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