# Calculating $\sum_{i=1}^a \lfloor a/i \rfloor i^2$

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.

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).

• 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? Mar 7 '18 at 19:07
• @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).
– D.W.
Mar 7 '18 at 19:46
• 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? Mar 8 '18 at 22:04
• @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$.
– D.W.
Mar 9 '18 at 0:33