# Can this upper bound for $\sum_{i=1}^n \lfloor \sqrt{p_i} \rfloor, p_i \in \Bbb P$ be improved?

I would like to find the smallest possible upper bound for the following sum of prime radicals (OEIS A062048):

$\sum_{i=1}^n \lfloor \sqrt{p_i} \rfloor, p_i \in \Bbb P$

This is my attempt. It is too big, I am sure there is a better way of calculating this, but my knowledge is not very good (the questions are at the end of the explanation):

$\sum_{i=1}^n \lfloor \sqrt{p_i} \rfloor = \lfloor \sqrt{2} \rfloor + \lfloor \sqrt{3} \rfloor + ... + \lfloor \sqrt{p_n} \rfloor$

by Bertrand's postulate $\lfloor \sqrt{p_{i+1}} \rfloor \lt \lfloor \sqrt{2 \cdot p_i} \rfloor$ so it is possible to replace in a first step $\lfloor \sqrt{3} \rfloor$ by $\lfloor \sqrt{2 \cdot 2} \rfloor$:

$\lfloor \sqrt{2} \rfloor + \lfloor \sqrt{3} \rfloor + ... + \lfloor \sqrt{p_n} \rfloor \lt \lfloor \sqrt{2} \rfloor + \lfloor \sqrt{2 \cdot 2} \rfloor + ... + \lfloor \sqrt{p_n} \rfloor$

then recursively doing the same with the next prime $\lfloor \sqrt{5} \rfloor \lt \lfloor \sqrt{2\cdot 3} \rfloor \lt \lfloor \sqrt{2\cdot (2 \cdot 2)} \rfloor$, etc. the result is:

$\lfloor \sqrt{2} \rfloor + \lfloor \sqrt{3} \rfloor + ... + \lfloor \sqrt{p_i} \rfloor... \lt \lfloor \sqrt{2} \rfloor + \lfloor \sqrt{2^2} \rfloor + \lfloor \sqrt{2^3} \rfloor + ... + \lfloor \sqrt{2^n} \rfloor =$

$=\sum_{i=1}^{n \ even}2^{\frac{n}{2}}+\sqrt{2}\cdot \sum_{i=1}^{n \ odd}2^{\frac{n-1}{2}}=$

$\sqrt{2} \lt 2$:

$\sum_{i=1}^{n \ even}2^{\frac{n}{2}}+\sqrt{2}\cdot \sum_{i=1}^{n \ odd}2^{\frac{n-1}{2}} \lt 2 \cdot \sum_{i=1}^n 2^{\frac{n}{2}}$

Finally, $\sum_{i=1}^n 2^i = (2^{i+1}-1)-2^0 = 2^{i+1}-2$, thus:

$2 \cdot \sum_{i=1}^n 2^{\frac{n}{2}} \lt 2 \cdot (2^{(\frac{n}{2}+1)}-2)=2^{(\frac{n}{2}+2)}-4$

So finally the expression would be:

$\sum_{i=1}^n \lfloor \sqrt{p_i} \rfloor, p_i \in \Bbb P \lt 2^{(\frac{n}{2}+2)}-4$

I would like to ask the following questions:

1. Are the calculations correct or there are gaps / errors?

2. Is there a better approach? Thank you!

UPDATE 2016/7/17: Thank you very much for the answers, for the sake of completeness I have sketched the solutions everybody kindly provided, compared with $\sum_{i=1}^{n}i=\frac{n \cdot (n+1)}{2}$. The reason is that this sequence is expected to grow slower than the sequence of the sum of the first $n$ elements, so it is a good expression to compare with. The only solution that was too big was mine, kindly improved by mathlove, that is why I wanted to ask for better values really under the value of the sum of the first $n$ natural numbers.

Blue: $\sum_{i=1}^{n}i=\frac{n \cdot (n+1)}{2}$

Red (mathlove) = $\sum_{i=1}^{n}\sqrt{p_i}\lt \sum_{i=1}^{n}2^{\frac i2}=\frac{2^{\frac{n+1}{2}}-\sqrt 2}{\sqrt 2-1}$

Yellow (Marco Cantarini) = $n\sqrt{n\log\left(n\right)+n\log\left(\log\left(n\right)\right)}-\frac{2\left(n-1\right)\sqrt{n-1}}{3\sqrt{\log\left(2\right)}}+1$

Green (LeGrandDODOM) (leading term only): $\displaystyle\frac 23 n^{\frac 32}\sqrt{\ln n}$

## 3 Answers

$\lfloor \sqrt{2} \rfloor + \lfloor \sqrt{3} \rfloor + ... + \lfloor \sqrt{p_i} \rfloor... \lt \lfloor \sqrt{2} \rfloor + \lfloor \sqrt{2^2} \rfloor + \lfloor \sqrt{2^3} \rfloor + ... + \lfloor \sqrt{2^n} \rfloor =$ $=\sum_{i=1}^{n \ even}2^{\frac{n}{2}}+\sqrt{2}\cdot \sum_{i=1}^{n \ odd}2^{\frac{n-1}{2}}=$

Then, you used $\sqrt{2} \lt 2$, but I think you don't need to do so because $$\sqrt 2\times 2^{\frac{n-1}{2}}=2^{\frac{n}{2}}$$ so the sum can be written as

$$\sum_{i=1}^{n}2^{\frac i2}\tag1$$

(By the way, it seems that you have $$\sum_{i=1}^n 2^{\frac{i}{2}} =2^{(\frac{n}{2}+1)}-2$$ but this is incorrect. See when $n=1$.)

Finally, from $(1)$, $$\sum_{i=1}^{n}\sqrt{p_i}\lt \sum_{i=1}^{n}2^{\frac i2}=\frac{2^{\frac{n+1}{2}}-\sqrt 2}{\sqrt 2-1}$$

• thank you for your corrections and improvement... may I ask you one final question? my reduction to get the upper bound is based on Bertrand's postulate... do you think that it could be improved by choosing another bound? I was thinking about Harman and Pintz (2011), where $p_{i+1} \lt p_i+p_i^{\frac{25}{1000}}$... but doing that recursive replacement the expressions gets too hard to work... – iadvd Jul 6 '16 at 9:28
• @iadvd: I think it might be but I don't have any good idea now. I'll keep considering because I'm interested in this too. – mathlove Jul 6 '16 at 10:07

Some asymptotics that should lead to a better bound with some additional work

From $p_n\sim n\ln n$ you can derive $\lfloor \sqrt{p_n} \rfloor\sim \sqrt{ n\ln n}$

Since $\sum_i \lfloor \sqrt{p_i} \rfloor$ diverges, the asymptotics above imply

$$\sum_{i=1}^n \lfloor \sqrt{p_i} \rfloor \sim \sum_{i=1}^n\sqrt{ i\ln i}$$

This last sum can be estimated via integrals, yielding

$$\sum_{i=1}^n \lfloor \sqrt{p_i} \rfloor \sim \int_1^n \sqrt{ t\ln t} dt$$

Integrating by parts, $\displaystyle \int_1^n \sqrt{ t\ln t} dt = \frac 23 n^{\frac 32}\sqrt{\ln n}-\int_1^n \sqrt{ \frac{t}{\ln t}} dt$

Since $\displaystyle \sqrt{ \frac{t}{\ln t}}dt = o\left( \sqrt{ t\ln t} \right)$ and $\int_1^\infty \sqrt{ t\ln t} dt = \infty$,

$$\displaystyle \int_1^n \sqrt{ \frac{t}{\ln t}} dt = o\left(\int_1^n \sqrt{ t\ln t} dt \right)$$

Therefore, $\displaystyle \int_1^n\sqrt{ \frac{t}{\ln t}}dt \sim \frac 23 n^{\frac 32}\sqrt{\ln n}$

and $$\sum_{i=1}^n \lfloor \sqrt{p_i} \rfloor \sim\frac 23 n^{\frac 32}\sqrt{\ln n}$$

As a result, you should expect a sharp upper bound to have $\displaystyle\frac 23 n^{\frac 32}\sqrt{\ln n}$ as its leading term.

We can obtain a better bound. We need first some preliminary result:

Proposition 1:$$\sum_{k=1}^{N}\sqrt{k}\in\left(\frac{2}{3}N\sqrt{N},\frac{4N+3}{6}N\sqrt{N}\right).$$ Proof: Let $$S=\sum_{k=1}^{N}\sqrt{k}$$ using Abel's summation and the bound $t-1\leq\left\lfloor t\right\rfloor \leq t$ we have $$S=N\sqrt{N}-\int_{1}^{N}\frac{\left\lfloor t\right\rfloor }{t}dt>\frac{2}{3}N\sqrt{N}$$ $$S<\frac{4N+3}{6}N\sqrt{N}.\square$$ The second thing we need is the Rosser's theorem and the last thing is the bound $p_{n}<n\log\left(n\right)+n\log\left(\log\left(n\right)\right),n>5$. Now we can study our sum. We have, using partial summation, $$\sum_{i\leq n}\left\lfloor \sqrt{p_{i}}\right\rfloor \leq\sum_{i\leq n}\sqrt{p_{i}}=n\sqrt{p_{n}}-\sum_{i=1}^{n-1}i\left(\sqrt{p_{i+1}}-\sqrt{p_{i}}\right)$$ $$=n\sqrt{p_{n}}-\sum_{i=1}^{n-1}i\left(\frac{p_{i+1}-p_{i}}{\sqrt{p_{i+1}}+\sqrt{p_{i}}}\right)\leq n\sqrt{p_{n}}-\sum_{i=1}^{n-1}\frac{i}{\sqrt{p_{i}}}$$ $$<n\sqrt{p_{n}}-\sum_{i=2}^{n-1}\sqrt{\frac{i}{\log\left(i\right)}}\leq n\sqrt{p_{n}}-\frac{1}{\sqrt{\log\left(2\right)}}\frac{2}{3}\left(n-1\right)\sqrt{n-1}+1$$ $$\color{red}{<n\sqrt{n\log\left(n\right)+n\log\left(\log\left(n\right)\right)}-\frac{2\left(n-1\right)\sqrt{n-1}}{3\sqrt{\log\left(2\right)}}+1},\, n>5.$$

• Why the downvote? A downvote without a comment is quite unconstructive. – Marco Cantarini Jul 6 '16 at 13:04
• I upvoted your answer not sure about the reason why somebody downvoted. Thank you for the calculation, it is very appreciated! – iadvd Jul 6 '16 at 14:15
• I have added a graph with the solutions, yours is what I was looking for, to be able to confirm that the bound is under $\sum_{i=1}^{n}i=\frac{n \cdot (n+1)}{2}$. Thank you again! – iadvd Jul 7 '16 at 0:02
• @iadvd You're welcome. – Marco Cantarini Jul 7 '16 at 7:46