Evaluating the sum $\sum_{i=1}^n i^2\cdot\lfloor{\frac ni}\rfloor$

I need to evaluate the sum $$\sum_{i=1}^n i^2\cdot\lfloor{\frac ni}\rfloor$$ After a little bit of math I found that the above sum is equal to: $$\sum_{i=1}^n i\cdot n - \sum_{i=1}^ni\cdot (n\space mod \space i)$$ The first (left) sum has a closed form, $\frac {n^2\cdot (n+1)}{2}$, but what about the left?

I need this for computational use, for very large $n$, so performing the summation with $O(n)$ is probably the wrong approach, which is why I suspect it has a closed form, or at least another way to perform the summation with smaller complexity, perhaps $O(\sqrt n)$. If the sum to the right has no closed form, then is there any other way to evaluate the original sum?

Solution 1:

Regarding an $O(n^{1/2+\epsilon})$ computation... one can use $$\sum_{m=1}^{n}f(m)g(\lfloor n/m\rfloor)=\sum_{m=1}^{\lfloor n/(k+1)\rfloor}f(m)g(\lfloor n/m\rfloor)+\\+\sum_{r=1}^{k}g(r)\big(F(\lfloor n/r\rfloor)-F(\lfloor n/(r+1)\rfloor)\big),$$ where $f,g$ are functions of positive integers, $1\leqslant k\leqslant n$, and $F(n)=\displaystyle\sum_{m=1}^{n}f(m)$.

(Put $f(n)=n^2$, $g(n)=n$, $F(n)=n(n+1)(2n+1)/6$ and $k=\lfloor\sqrt{n}\rfloor$, say.)

UPDATE. The equation above is obtained as follows. If $1\leqslant m,r\leqslant n$ then $$\Big\lfloor\frac{n}{m}\Big\rfloor=r\iff mr\leqslant n<m(r+1)\iff\Big\lfloor\frac{n}{r+1}\Big\rfloor<m\leqslant\Big\lfloor\frac{n}{r}\Big\rfloor.$$ So, for $1\leqslant k\leqslant n$, splitting the range of summation in $\displaystyle\sum_{m=1}^{n}f(m)g(\lfloor n/m\rfloor)$ this way: $$\{m : 1\leqslant m\leqslant n\} = \left\{m : 1\leqslant m\leqslant\Big\lfloor\frac{n}{k+1}\Big\rfloor\right\}\cup\bigcup_{r=1}^{k}\left\{m : \Big\lfloor\frac{n}{r+1}\Big\rfloor<m\leqslant\Big\lfloor\frac{n}{r}\Big\rfloor\right\},$$ we get the expected.

Solution 2:

Letting the summation begin with $i=1$ we obtain the sequence $$1, 6, 16, 37, 63, 113, 163, 248, 339, 469, 591, 801, 971, 1221, 1481, \ 1822, 2112, 2567, 2929, 3475\ \ldots$$ This sequence is listed under A064602 at OEIS and is the sequence of partial sums of A001157. What they are saying at OEIS is not very hopeful for a simple expression producing this sequence.