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

  • 1
    $\begingroup$ what do you mean while saying "discretization corrections, which can be computed"? Computed as rational number? Many doubts. Estimated nicely? But then what is definition of "nice" estimate, which probably would be ok in a problem with floors too? $\endgroup$ – Fedor Petrov Dec 5 '10 at 11:24
  • $\begingroup$ To piggyback on Fedya's comment, the difference between the sums with and without the floor is bounded by $(x-1)N$, which is considerably less than the main term. How does it compare to the error term? $\endgroup$ – Gerry Myerson Dec 5 '10 at 11:50
  • $\begingroup$ I'd like to have an exact answer, but even a good approximation of the floor error term could point me in the right direction. For integer x without the floor, I get the following (N^2 ln x + (1+1/x)*N/2 + (1-1/(x*x))/12) which seems to approximate the exact sum to a better than 1/N accuracy. The floor introduces an error term with the magnitude ~sqrt(N). $\endgroup$ – user11325 Dec 5 '10 at 12:33
  • 2
    $\begingroup$ As a side comment, the sum resembles in a way Legendre's formula for counting primes mathworld.wolfram.com/LegendresFormula.html. You are counting integers up to $N^2$ that are divisible by $N$,...,$xN$, with multiplicities. Perhaps, like in Legendre's formula, there is an inclusion-exclusion approach to this. If that works though, the sum might be reduced to functions like $\pi(N^2)$, explaining the strange fluctuations in the error term but proving that it will be difficult to get an exact answer :) $\endgroup$ – Tim Dokchitser Dec 5 '10 at 14:54
  • 1
    $\begingroup$ it may be helpful mathworld.wolfram.com/DirichletDivisorProblem.html $\endgroup$ – Fedor Petrov Dec 5 '10 at 18:51

The following reduces the number of terms that you are adding up, from about $(x-1)N$ to about $N(1-1/x)$ (i.e, by a factor of $x$). So it should speed up your calculations some. Unfortunately, the number of terms is still $O(N)$, and so it won't reduce the asymptotic run time, but maybe it will still be useful.

$$\sum_{k=N}^{xN} \left\lfloor \frac{N^2}{k} \right\rfloor = \sum_{k=\lfloor N/x \rfloor +1}^N \left\lfloor \frac{N^2}{k} \right\rfloor + N - xN \left\{ \frac{N}{x}\right\},$$ where $\{y\}$ denotes the fractional part of $y$.

This is an application of the following "fun" result I published with Natalio Guersenzvaig a few years ago: $$\sum_{d=j+1}^{k} \lfloor n/d \rfloor - \sum_{d= \lfloor n/k \rfloor + 1}^{\lfloor n/j \rfloor} \lfloor n/d \rfloor = k \lfloor n/k \rfloor - j \lfloor n/j \rfloor.$$ (This is Corollary 4 in "Some Inversion Formulas for Sums of Quotients," Crux Mathematicorum, 32 (1): 39-43, 2006.)


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.