5
$\begingroup$

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

Improve this question
$\endgroup$
5
  • 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
    Commented Dec 5, 2010 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
    Commented Dec 5, 2010 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
    Commented Dec 5, 2010 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
    Commented Dec 5, 2010 at 14:54
  • 1
    $\begingroup$ it may be helpful mathworld.wolfram.com/DirichletDivisorProblem.html $\endgroup$
    – Fedor Petrov
    Commented Dec 5, 2010 at 18:51

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .