3
$\begingroup$

Is there a way to calculate the following sum for large $c > K$, closed-form or approximation ?: $$ \sum_{n = 1}^{c}\left\{\sqrt{\,{K + n^{2}}\,}\right\} $$ where $K$ and $n$ are positive integers and $\left\{\cdots\right\}$ indicates the Fractional Part.

A similar question.

$\endgroup$
3
  • $\begingroup$ Hint: when $n$ is large compared to $\sqrt K$ then $\sqrt{K+n^2}-n \sim \frac{K}{2n}$. $\endgroup$ Commented Aug 22, 2021 at 20:30
  • $\begingroup$ @RuanSunkel are you satisfied with my answer? $\endgroup$
    – fwd
    Commented Aug 24, 2021 at 13:20
  • $\begingroup$ Hi @fwd, I am still busy digesting. So far I am happy with the answer, I learned a lot. Looking at the question and the answer, I think what I am really interested in is the $\mathcal{O}(1)$ term in $\sum_2$, calculating it given a specific $K$ and $c$, so basically calculating the actual value of $\sum_2$. Thinking of maybe asking a follow up question. $\endgroup$ Commented Aug 24, 2021 at 14:14

3 Answers 3

2
$\begingroup$

The given sum can be written as $$ \Sigma = \Sigma_1 - \Sigma_2 $$ where $$ \Sigma_1 = \sum_{n=1}^{c} \sqrt{n^2 + K} $$ and $$ \Sigma_2 = \sum_{n=1}^{c} \lfloor\sqrt{n^2 + K}\rfloor. $$ Now using $H_n = \log n + \gamma + \mathcal{O}(1/n)$ where $H_n$ is the $n$-th harmonic number, \begin{align*} \sum_{n=1}^{c} \sqrt{n^2 + K} - n &= \sum_{n=1}^c \frac{K}{\sqrt{n^2 + K} + n} \\ &\le \frac{K}{2} \sum_{n=1}^{c} \frac{1}{n} = \frac{K}{2}(\log c + \gamma + \mathcal{O}(1/c)). \end{align*} Hence $$ \Sigma_{1} = \sum_{n=1}^{c} \sqrt{n^2 + K} = \frac{1}{2}c(c+1) + \frac{K}{2}(\log c + \gamma) + \mathcal{O}(1/c) $$

Let $A = \lfloor\sqrt{K+1} - 1\rfloor$. Then, \begin{align*} \Sigma_{2} = \sum_{n=1}^{c} \lfloor\sqrt{n^2 + K}\rfloor &= \sum_{j=1}^{A}\sum_{\frac{K-(j+1)^2}{2(j+1)} < n \le \frac{K-j^2}{2j}}(n+j) + \sum_{\frac{K-1}{2} < n \le c}n \\ &= \sum_{n=1}^c n + \sum_{j=1}^{A}\sum_{\frac{K-(j+1)^2}{2(j+1)} < n \le \frac{K-j^2}{2j}}j\\ &= \frac{1}{2}c(c+1) + \sum_{j=1}^A j\left(\frac{3}{2} + \frac{K}{2j(j+1)}+ \mathcal{O}(1)\right)\\ &= \frac{1}{2}c(c+1) + \frac{3}{4}A(A+1) + \frac{K}{2}(H_A - 1) + \mathcal{O}\left(\sum_{j=1}^A j\right)\\ &= \frac{1}{2}c(c+1) + \frac{3}{4}A(A+1) + \frac{K}{2}(H_A - 1) + \mathcal{O}(1) \end{align*} since $\mathcal{O}\left(\sum_{j=1}^A j\right) = \mathcal{O}(K) = \mathcal{O}(1)$.

Thus,

\begin{align*} \Sigma &= \frac{K}{2}(\log c + \gamma) - \frac{3}{4}A(A+1) - \frac{K}{2}(H_A - 1) + \mathcal{O}(1).\\ \end{align*}

$\endgroup$
6
  • $\begingroup$ Hi, thank you for the answer. I did a quick test and $\sum_2$ seems to be different than expected. For example, with $K=15$, and $c=16$, $\sum_2=146$, but $\sum_2$ provided in the answer gives $\sum_2=2822$. Please correct me if I am missing something. $\endgroup$ Commented Aug 22, 2021 at 18:14
  • $\begingroup$ you're right, something's wrong $\endgroup$
    – fwd
    Commented Aug 22, 2021 at 19:07
  • $\begingroup$ @RuanSunkel I have edited my answer. $\endgroup$
    – fwd
    Commented Aug 23, 2021 at 6:33
  • $\begingroup$ Thank you @fwd. Can you please elaborate on the $\mathcal{O}(1)$ constant that depends on $K$? $\endgroup$ Commented Aug 23, 2021 at 17:57
  • $\begingroup$ @RuanSunkel I added more details to show where the $\mathcal{O}(1)$ term comes from. The larger $K$ is, the larger this term is. Numerical plots suggest that it grows linearly in $K$. But since $K$ is fixed, it's just $\mathcal{O}(1)$ $\endgroup$
    – fwd
    Commented Aug 23, 2021 at 18:27
0
$\begingroup$

Partial solution: If we follow the example from Find a formula for $\sum\limits_{k=1}^n \lfloor \sqrt{k} \rfloor$. Then we have integer values for some integer $p$ where $p \le \sqrt{{k}^{2} + n} < p + 1 \Longleftrightarrow {p}^{2} \le {k}^{2} + n < \left({p + 1}\right)^{2} \Rightarrow p = \lfloor{\sqrt{{k}^{2} + n}}\rfloor$, or

$$ \sqrt{{p}^{2} - n} \le k < \sqrt{\left({p + 1}\right)^{2} - n} \Rightarrow 1 \le \lceil{\sqrt{{p}^{2} - n}}\rceil \le k \le \lceil{\sqrt{\left({p + 1}\right)^{2} - n}}\rceil - 1 \le c. $$

The maximum $p$ index is given by $\sqrt{{c}^{2} + n} < p + 1$ or ${p}_{max} = \lfloor{\sqrt{{c}^{2} + n}}\rfloor$ while the minimum $p$ index is ${p}_{min} = \lfloor{\sqrt{n +1}}\rfloor$. Also the lower $k$ index Iverson bracket constraint is needed to ensure that ${p}^{2} \ge n$, and the upper $k$ index constraint is to ensure that ${k}_{max} \le c$. So we can write

$$ \begin{aligned} {\Sigma}_{2} = \sum_{k = 1}^{c} \lfloor{\sqrt{{k}^{2} + n}}\rfloor {}={} & \sum_{p = \lfloor{\sqrt{n + 1}}\rfloor}^{\lfloor{\sqrt{{c}^{2} + n}}\rfloor} \sum_{k = \max \left({1, \lceil{\sqrt{{p}^{2} - n}}\rceil \left[{{p}^{2} \ge n}\right]}\right)}^{\min \left({c, \lceil{\sqrt{\left({p + 1}\right)^{2} - n}}\rceil - 1}\right)} \lfloor{\sqrt{{k}^{2} + n}}\rfloor \\ {}={} & \sum_{p = \lfloor{\sqrt{n + 1}}\rfloor}^{\lfloor{\sqrt{{c}^{2} + n}}\rfloor} p \sum_{k = \max \left({1, \lceil{\sqrt{{p}^{2} - n}\rceil} \left[{{p}^{2} \ge n}\right]}\right)}^{\min \left({c, \lceil{\sqrt{\left({p + 1}\right)^{2} - n}}\rceil - 1}\right)} 1 \\ {}={} & \sum_{p = \lfloor{\sqrt{n + 1}}\rfloor}^{\lfloor{\sqrt{{c}^{2} + n}}\rfloor} p \begin{bmatrix} 1 + \min \left({c, \lceil{\sqrt{\left({p + 1}\right)^{2} - n}}\rceil - 1}\right) \\ \mathop{-} \max \left({1, \lceil{\sqrt{{p}^{2} - n}}\rceil \left[{{p}^{2} \ge n}\right]}\right) \end{bmatrix}. \end{aligned} $$

At this point the remaining sums can be approximated using the Euler Maclaurin formula after dropping the floor and ceiling functions, and taking the dominant argument of the max and min argument lists. This will generate asymptotic expansions.

This solution holds for all values of $c$.

$\endgroup$
-1
$\begingroup$

Upon further telescoping sum expansions and simplifications we can write for $c \ge \lfloor{(n-1)/2}\rfloor$ and with asymptotic expansions as $n \rightarrow \infty$

$${\Sigma}_{2} = \frac{1}{2}\, c \left({c + 1}\right) + \sum_{j = 1}^{A} \lfloor{\frac{K - {j}^{2}}{2\, j}}\rfloor \approx \frac{1}{2}\, {c}^{2} + \frac{1}{2}\, c + \frac{1}{4}\, K\, \log \left({K}\right) + \frac{1}{4} \left({2\, \gamma - 1}\right) K + \frac{11}{24} - \frac{49}{240}\, \frac{1}{K} + \frac{197}{1{,}260}\, \frac{1}{{K}^{2}} - \frac{421}{3{,}360}\, \frac{1}{{K}^{3}} + O \left({\frac{1}{{K}^{4}}}\right). $$

Which is exact. However, so far I can't find the correct summation for $c < \lfloor{(K-1)/2}\rfloor$.

See How to show that $\sum_{j = 1}^{A \left({n}\right)} \left\{{\frac{n - {j}^{2}}{2\, j}}\right\}$ satisfies Weyl's criterion. for a related question to solving the fractional part of the above floor sum. A change of variables, $K = n$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .