1
$\begingroup$

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?

$\endgroup$
3
  • 4
    $\begingroup$ 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. $\endgroup$ – S. Carnahan Jul 6 '14 at 8:36
  • $\begingroup$ Thanks the links.but I think the n is a integer.it can be read in O(1). $\endgroup$ – WeiRong Xu Jul 6 '14 at 8:57
  • 1
    $\begingroup$ 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)$? $\endgroup$ – Emil Jeřábek Jul 6 '14 at 11:37
7
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ $n^2-\sum_{i\le n}\sigma(i)$ is actually $\sum_{i\le n}(n\bmod i)$ rather than $f(n)$, right? I must say that I don’t understand how the OP intends to use the former to compute the latter, but anyway, $f(n)=\sum_{i\le n}\tau(i)$, which seems not to be directly covered by your paper. $\endgroup$ – Emil Jeřábek Jul 6 '14 at 10:51
  • $\begingroup$ Thanks, Emil, I spaced out. Too early in the morning! I corrected it. $\endgroup$ – Jeffrey Shallit Jul 6 '14 at 12:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.