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?
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityI 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?
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.