Sums involving floor function I am looking for a direct formula for this sum
$$\sum_{k=0}^n \lfloor{\sqrt{n+k}}\rfloor\lfloor{\sqrt{k}}\rfloor$$
Or a method to efficiently compute the sum for large n

Here's an exact $O(\sqrt{n})$ formula:
$$\left\lfloor \sqrt{n}\right\rfloor  \left((n+1) \left\lfloor \sqrt{n}\right\rfloor +\frac{1}{3} \left(-\left(\left\lfloor \sqrt{n}\right\rfloor +1\right)^3+\frac{3}{2} \left(\left\lfloor \sqrt{n}\right\rfloor +1\right)^2+\frac{1}{2} \left(-\left\lfloor \sqrt{n}\right\rfloor -1\right)\right)\right)+\frac{1}{6} \left\lfloor \sqrt{n}\right\rfloor  \left(-\left\lfloor \sqrt{n}\right\rfloor  \left(2 \left\lfloor \sqrt{n}\right\rfloor +3\right)+6 n+5\right) \left\lfloor \sqrt{2} \sqrt{n}-\left\lfloor \sqrt{n}\right\rfloor \right\rfloor +\sum _{j=\left\lfloor \sqrt{n}\right\rfloor +1}^{\left\lfloor \sqrt{2n} \right\rfloor } \left(\left\lfloor \sqrt{j^2-n}\right\rfloor ^3-\left(j^2-n\right) \left\lfloor \sqrt{j^2-n}\right\rfloor -\frac{1}{6} \left(\left\lfloor \sqrt{j^2-n}\right\rfloor -1\right) \left(4 \left\lfloor \sqrt{j^2-n}\right\rfloor +1\right) \left\lfloor \sqrt{j^2-n}\right\rfloor \right)$$
It can be derived via the following steps:


*the $\left\lfloor\sqrt{k+n}\right\rfloor$ factor can be ignored at first; substitute in $\sqrt{n}$ and use the known formula for summing $\left\lfloor\sqrt{k}\right\rfloor$

*now add in the deficit:  each $k$ where $\left\lfloor\sqrt{k+n}\right\rfloor$ increases by $1$ (there are $O(\sqrt{n})$ such points), sum $\left\lfloor\sqrt{k}\right\rfloor$ from this $k$ to $n$ (use the known formula again, with suitable modifications).

*Clean up: shift the summation index to make the sum formula maybe nicer looking; pull factors which only depend on $n$ outside the sum, etc.

