# How can I calculate $\sum_{i=1}^{n} (n \bmod i)$

I want to calculate the sum

$$\sum_{i=1}^{n} \left\lfloor\frac{n}{i}\right\rfloor,$$

and it seems to require to calculate the sum $$\sum_{i=1}^{n} (n \bmod i).$$

How can I get an $O(1)$ solution instead of the $O(n)$ solution?

• It's pretty easy to get $O(n^{1/2 + o(1)})$ using symmetry, and section 2.1 of arxiv.org/abs/1009.3956 gives an $O(n^{1/3 + o(1)})$ algorithm. $O(1)$ is quite impossible, since you can't even read the digits of $n$ in $O(1)$ time. See math.stackexchange.com/questions/740442/… for some theoretical background. Jul 6 '14 at 8:36
• Thanks the links.but I think the n is a integer.it can be read in O(1). Jul 6 '14 at 8:57
• How is computing $\sum_{i\le n}\lfloor n/i\rfloor=nH_n-\sum_{i\le n}\frac{n\bmod i}i$ related to computing $\sum_{i\le n}(n\bmod i)$? Jul 6 '14 at 11:37

You're probably not going to be able to compute $\sum_{1 \leq i \leq n} n \bmod i$ efficiently. Let $f(n)$ denote this sum. This is sequence A004125 in Sloane's Online Encyclopedia of integer sequences (see http://oeis.org/A004125 ). It is known and relatively simple to prove that $f(n) = n^2 - \sum_{1 \leq i \leq n} \sigma(i)$, where $\sigma$ is the sum of divisors function.

So if you could compute $f(n)$ efficiently, then (by considering $f(n)-f(n-1)$), you'd be able to compute $\sigma(n)$ efficiently. But an old result of mine (with Gary Miller and Eric Bach, in SIAM J. Computing in 1986), computing $\sigma(n)$ is random-polynomial-time equivalent to factoring $n$. So unless there is an efficient algorithm for factoring...

Also, as Emil points out, $g(n) = \sum_{1 \leq i \leq n} \lfloor n/i \rfloor$ equals $\sum_{1 \leq i \leq n} \tau(i)$, where $\tau$ is the number of divisors function. An efficient algorithm for $g(n)$ would allow fast computation of $\tau(n)$, and nobody knows how to compute $\tau(n)$ efficiently, either.

In everything I said above, "efficiently" means polynomial time in $\log n$.

By the way, S. Carnahan's answer is correct, but you and he are using different computational models. You seem to want to use the unit-cost model, which is not appropriate when dealing with computations involving integers.