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$ 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$
0

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.