sum of floor ("weighted" divisor summary function)

Question

is there a closed form for $$ \sum_{i=1}^N\left\lfloor\frac{N}{i}\right\rfloor i $$ Or is there any faster way to calculate this for any given N value?

Answer 1

This answer does not give closed form formula (for reasons mentioned in comments), but it gives a way to calculate the sum more efficiently than just going through all $i\leq N$.

The trick is that values of $\left\lfloor\frac{N}{i}\right\rfloor$ do not change for long ranges of $i$, for example:

$$ \left\lfloor\frac{10}{6}\right\rfloor = \left\lfloor\frac{10}{7}\right\rfloor = \dots = \left\lfloor\frac{10}{10}\right\rfloor = 1. $$

This can be used to skip over these and sum them all in one iteration. Since you have $$ \left\lfloor\frac{N}{i}\right\rfloor = k \Leftrightarrow \frac{N}{k+1} < i \leq \frac{N}{k} $$ all you need to do is iterate from current $i$ to next different value which will be $\left\lfloor\frac{N}{k}\right\rfloor+1$.

For example one can define \begin{align*} k_n&=\left\lfloor\frac{N}{i_{n-1}}\right\rfloor\\ i_n&=\left\lfloor\frac{N}{k_n}\right\rfloor+1\\ s_n&=s_{n-1}+\sum_{i=\left\lfloor\frac{N}{k_n+1}\right\rfloor+1}^{\left\lfloor\frac{N}{k_n}\right\rfloor} k_n = s_{n-1}+\frac{1}{2}k_n\Bigl(\left\lfloor\frac{N}{k_n+1}\right\rfloor+\left\lfloor\frac{N}{k_n}\right\rfloor+1\Bigr)\Bigl(\left\lfloor\frac{N}{k_n}\right\rfloor-\left\lfloor\frac{N}{k_n+1}\right\rfloor\Bigr) \end{align*}

with $k_0=0,s_0=0,i_0=1$. Then just iterating while $i_n \leq N$, resulting sum is then $s_{n+1}$.

Example for $N=10$:

\begin{align*} k_0&=0&s_0&=0&i_0&=1\\ k_1&=10&s_1&=10&i_1&=2\\ k_2&=5&s_2&=20&i_2&=3\\ k_3&=3&s_3&=29&i_3&=4\\ k_4&=2&s_4&=47&i_4&=6\\ k_5&=1&s_5&=87&i_5&=11\\ \end{align*} So result is $87$ and only $5$ iterations were needed. For $N=100$ it takes $19$ iterations, for $N=1000$ it takes $62$, etc...

Answer 2

Maybe you can simplify something from here $n = m\lfloor \frac{n}{m}\rfloor + ( n \mod m)$, i.e. you can factor $N$ and this may simplify the sum for $N$ not too large.