Summation of floor of harmonic progression multiply with i : $\sum_{i=2}^n i\cdot\lfloor\frac ni\rfloor$

Question

Summation of floor of harmonic progression multiply with $i$:

$$\sum_{i=2}^n i\cdot\left\lfloor\frac ni\right\rfloor$$

This actually from a programming question. This formula is required to compute solution faster. But I can't figure out this solution.

Answer 1

This is effectively OEIS sequence A024916. There seems to be no formula for the terms.

Answer 2

As a continuation of the comment I left (using this answer). Using division with remainder, if $n=q_ii+r_i$ s.t. $0\leq r_i < i$, then $$r_i=n \pmod{i}$$ $$q_i=\left \lfloor \frac{n}{i} \right \rfloor$$ $$r_i=n-i\left \lfloor \frac{n}{i} \right \rfloor$$ Thus, $$\sum_{i=2}^n i\cdot\left\lfloor\frac ni\right\rfloor= \sum_{i=2}^n (n-r_i)= n(n-1)-\sum_{i=2}^n r_i =\\ n(n-1)-\sum_{i=2}^n \left(n \pmod{i}\right)$$

I am not sure what do you mean by "faster", but I presume computing $n \pmod{i}$ is faster than $i \cdot ...$ and $\left\lfloor\frac ni\right\rfloor$.

From the same link, it is relatively easy to see that $$\sum_{i=1}^n i\cdot\left\lfloor\frac ni\right\rfloor= n^2-\sum_{i=1}^n \left(n \pmod{i}\right) \sim \\ n^2 - n^2\left(1-\frac{\pi^2}{12}\right)=n^2\frac{\pi^2}{12}$$ as per the link suggested by @Peter.