2
$\begingroup$

I have a sum:
$$S = \sum_{i=1}^n{\lfloor a/i \rfloor i^2},$$
where $a$ is a constant. Is there a way to speed this up? That is, can we avoid iterating overl all $i$s, possibly calculating it in logarithmic or better time, something manageable when $a$ is big, n = a/2? I tried lots with pen and paper, but I cannot see how to do this faster than $O(a)$ time.

$\endgroup$
4
$\begingroup$

The idea is to split the sum into two parts: For individual values of i for $i <= a^{1/2}$, then for individual values of floor (a/i). For example find the smallest and largest values i where floor (a/i) = 1 or 1 <= a/i < 2. The values i^2 can be summed with a simple formula.

Here's how we can do this efficiently:

We have $a/i ≥ k$ iff $i ≤ a/k$ or $i ≤ \lfloor a/k \rfloor$. Define $g(k) = \lfloor a/k \rfloor$, then $a/i ≥ k$ iff $i ≤ g(k)$.

We have $\lfloor a/i \rfloor = k$ iff $a/i ≥ k$ but not $a/i ≥ k + 1$, that is $i ≤ g(k)$ but not $i ≤ g(k+1)$, or $g(k+1) < i ≤ g(k)$.

Define $f(n) = (n \cdot (n+1) \cdot (2n+1))/6$, then the sum of squares from $1^2$ to $n^2$ is $f(n)$. The sum of the squares $i^2$ for $g(k+1) < i ≤ g(k)$ is $f(g(k)-f(g(k+1))$.

So the sum of $\lfloor a/i \rfloor \cdot i^2$ for all i such that $\lfloor a/i \rfloor = k$ is $k \cdot (f(g(k)-f(g(k+1)))$. We pick some m close to $a^{1/2}$. The sum of $\lfloor a/i \rfloor \cdot i^2$ for all i such that $\lfloor a/i \rfloor ≤ m$ equals $k \cdot (f(g(k)-f(g(k+1)))$, summed for 1 ≤ k ≤ m. This covers all $i > g(m+1)$.

To this sum we add $\lfloor a/i \rfloor \cdot i^2 = g(i) \cdot i2$ for 1 ≤ i ≤ g(m+1).

$\endgroup$
  • $\begingroup$ I like it. There are at most $\sqrt a$ distinct values of $\lfloor a/i \rfloor$ for $i > \sqrt a$, since $0 \le a/i < \sqrt a$ whenever $i > \sqrt a$, and there are at most $\sqrt a$ distinct integers in this range. I think this half might require binary searches though, adding a $\log a$ factor (not that that's a big deal). Or do you know a way to get these "$i$-steps" in constant time? $\endgroup$ – j_random_hacker Mar 7 '18 at 19:07
  • 1
    $\begingroup$ @j_random_hacker, given $j$, you should be able to find the largest $i$ and smallest $i$ such that $\lfloor a/i \rfloor = j$ in $O(1)$ time (I think you just need to divide, basically). $\endgroup$ – D.W. Mar 7 '18 at 19:46
  • $\begingroup$ Lets say n = a/2. OK, there there is at most $a^{1/2}$ distinct values of ${floor(a/i)}$, for ${i > sqrt(a)}$, how to find them? $\endgroup$ – Robert Hanigan Mar 8 '18 at 22:04
  • $\begingroup$ @TomaszMadry, the possible values are a subset of $1,2,3,\dots,\sqrt{a}$, so just try each possibility. For each such possibility -- call it $j$ -- you find the largest $i$ and smallest $i$ such that $\lfloor a/i \rfloor = j$. $\endgroup$ – D.W. Mar 9 '18 at 0:33

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.