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?
 A: 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.  
