This is sort of a borderline question that could fit here, in cstheory, or even on stackoverflow, but this site looks like the best bet.

Here's a sum:

$$\sum_{k=N}^{xN} \lfloor \frac{N^2}{k} \rfloor $$

where N is an integer and x is a small number, $x\\ll N$. (For simplicity, let's assume x=2.)

Without the floor function, this is more or less trivial, it's just $N^2 \ln{x}$ + discretization corrections, which can be computed. The floor function really throws the wrench in the works.

Does anyone know / can anyone think of an algorithm to compute the sum faster than $O(N)$?

There's a curious pattern in the differences between consecutive terms, it can be used to speed up the summation by a constant factor, but it does not seem to allow us to go below $O(N)$.