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}$

enter image description here


$\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}$$

  • $\begingroup$ 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... $\endgroup$
    – iadvd
    Jul 6 '16 at 9:28
  • 1
    $\begingroup$ @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. $\endgroup$
    – 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.$$

  • $\begingroup$ Why the downvote? A downvote without a comment is quite unconstructive. $\endgroup$ Jul 6 '16 at 13:04
  • $\begingroup$ I upvoted your answer not sure about the reason why somebody downvoted. Thank you for the calculation, it is very appreciated! $\endgroup$
    – iadvd
    Jul 6 '16 at 14:15
  • $\begingroup$ 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! $\endgroup$
    – iadvd
    Jul 7 '16 at 0:02
  • $\begingroup$ @iadvd You're welcome. $\endgroup$ Jul 7 '16 at 7:46

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.