How to calculate the sum of remainders of N?

One can use the Dirichlet hyperbola method to compute $\sum_{i \leq n} \sigma(i)$ in time $O( n^{1/2} )$ (up to logarithmic factors coming from arithmetic operations such as division):

\begin{align} \sum_{i \leq n} \sigma(i) &= \sum_{i \leq n} \sum_{d|i} d \\ &= \sum_{d,m: dm \leq n} d \\ &= \sum_{d \leq \sqrt{n}} d \sum_{\sqrt{n} < m \leq n/d} 1 + \sum_{m \leq \sqrt{n}} \sum_{d \leq n/m} d \\ &= \sum_{d \leq \sqrt{n}} d( \lfloor \frac{n}{d} \rfloor - \lfloor \sqrt{n}\rfloor ) + \sum_{m \leq \sqrt{n}} \frac{\lfloor\frac{n}{m}+1\rfloor \lfloor \frac{n}{m} \rfloor}{2}. \end{align}

One can obtain some small speedups (by a factor of $O(1)$) by collecting some like terms here.

One can improve this to $O(n^{1/2-c})$ for some small $c>0$ by approximating the hyperbola by a polygon: see the Polymath4 paper in which this was done for the sum $\sum_{i\leq n} \tau(i)$. Other than small improvements in $c$, I think this is the fastest algorithm currently known.

I found an article from Richard Sladkey, "A Successive Approximation Algorithm for computing the Divisor Summary Function", June 18, 2012 arXiv:1206.3369v1 [math.NT] 15 June 2012 where he shows that the solution can be computed in $\mathcal{O}(N^{1/3})$ steps. The paper introduces restricted divisor sums for part of this calculation.

According to the references in OEIS there isn't fast way unless I have missed something.

The fastest I saw is $a(n+1) = a(n) + 2n+1 - \sigma(n+1) $.