0
$\begingroup$

I'm trying to find a nicer form to evaluate this sum, but the floor function is throwing me off. $$\sum_{x=a}^b \left\lfloor {\frac{k}{x}} \right\rfloor$$ This is the most I've been able to do so far, but I'm wondering whether it's even a useful point to continue working from: $$\sum_{x=a}^b \left\lfloor {\frac{k}{x}} \right\rfloor = \sum_{x=a}^b \left( {\frac{k}{x}} \right) - \sum_{x=a}^b \left\{ {\frac{k}{x}} \right\} = k(H_b - H_{a-1}) - \sum_{x=a}^b \left\{ {\frac{k}{x}} \right\}$$ as there seems to be even less literature about the sum of a fractional part than there is about a sum of the floor function.

Is there any general technique to approaching a problem like this?

$\endgroup$
  • $\begingroup$ When specific bounds are placed on $a$ and $b$ estimating the sum of fractional parts like the one you mention are well known problems, for instance the unsolved Dirichlet divisor problem. $\endgroup$ – Ethan Sep 11 '14 at 18:24
1
$\begingroup$

I'm assuming $a$ and $b$ are natural numbers with $a\leq b$ and that $k$ is some real number greater then or equal to $1$, if so here are some different representations of your sum that you might find useful, in many instances these representations can be used to calculate your sum faster computationally or to get a better asymptotic estimate on your sum.

Now before we go any further we can assume with out a loss of generality that $k\ge a$.

If it is not then we will have $k<a<a+1<a+2<a+3\cdots <b-1<b$ which means that for any value of $x$ in the set $\{a, a+1, a+2, a+3\cdots b-1,b \}$ we will have $\frac{k}{x}<1\implies \lfloor \frac{k}{x}\rfloor=0$. Which means our entire sum will be equal to zero, and so were done.

Thus it comes down to dividing your sum into the two cases when $b\ge k$ and $b<k$.


We first start by using the Dirichlet hyperbola method so that we get:

$$\large{\sum_{x=1}^{\lfloor k \rfloor}\lfloor \frac{k}{x}\rfloor=- \lfloor y\rfloor\lfloor \frac{k}{y} \rfloor+\sum_{x=1}^{\lfloor y\rfloor}\lfloor \frac{k}{x}\rfloor+\sum_{x=1}^{\lfloor \frac{k}{y} \rfloor}\lfloor \frac{k}{x}\rfloor}$$

Now set $y=a-1$ and assume $a>1$, if it is not then you can always just set $a=2$ and add $\lfloor k \rfloor$ to both sides to give you the correct expressions.

We can then subtract the middle sum on the right from both sides which gives us:

$$\large{\sum_{x=a}^{\lfloor k \rfloor}\lfloor \frac{k}{x}\rfloor=-(a-1)\lfloor \frac{k}{a-1} \rfloor+\sum_{x=1}^{\lfloor \frac{k}{a-1} \rfloor}\lfloor \frac{k}{x}\rfloor}$$

Now suppose $b$ is greater then $k$, then for all $b>x>k$ we have $1>\frac{k}{x} \implies \lfloor \frac{k}{x} \rfloor=0$.

Thus $\sum_{x=a}^b\lfloor \frac{k}{x} \rfloor=\sum_{x=\lfloor k \rfloor+1}^b\lfloor \frac{k}{x} \rfloor+\sum_{x=a}^{\lfloor k \rfloor}\lfloor \frac{k}{x}\rfloor=0+\sum_{x=a}^{\lfloor k \rfloor}\lfloor \frac{k}{x}\rfloor=\sum_{x=a}^{\lfloor k \rfloor}\lfloor \frac{k}{x}\rfloor$

So we have if $b\ge k$:

$$\large{\sum_{x=a}^b\lfloor \frac{k}{x}\rfloor=-(a-1)\lfloor \frac{k}{a-1} \rfloor+\sum_{x=1}^{\lfloor \frac{k}{a-1} \rfloor}\lfloor \frac{k}{x}\rfloor}$$

And if $b<k$ subtracting the sum $\sum_{x=b+1}^{\lfloor k \rfloor}\lfloor \frac{k}{x}\rfloor$ from both sides gives:

$$\large{\sum_{x=a}^b\lfloor \frac{k}{x}\rfloor=-(a-1)\lfloor \frac{k}{a-1} \rfloor-\sum_{x=b+1}^{\lfloor k \rfloor}\lfloor \frac{k}{x}\rfloor+\sum_{x=1}^{\lfloor \frac{k}{a-1} \rfloor}\lfloor \frac{k}{x}\rfloor}$$


For example a special case is:

$$\large{ \sum_{x=1}^{b}\lfloor \frac{b}{x} \rfloor = -\lfloor \sqrt{b} \rfloor^2+2\sum_{x=1}^{ \lfloor \sqrt{b} \rfloor } } \lfloor \frac{b}{x} \rfloor$$

Notice how this turns our first sum of floor functions up to index $b$ into an expression involving the same floor functions but with a much smaller upper index of $\lfloor \sqrt{b} \rfloor$. This can be used to calculate the first sum much faster or to give a good asymptotic estimate on the sum.

$\endgroup$
0
$\begingroup$
  1. The best thing I know is to determine the domain of the variable.

  2. Then find the results of least integer function and fractional part for different parts of the domain.

  3. Then you get different results at different domains.

For example in your problem

$$\sum_{x=a}^b \left\lfloor {\frac{k}{x}} \right\rfloor$$

$x$ varies from $a$ to $b$.

  1. for all $x < a$ floor function will give you 0.

  2. for $x = a$ it gives 1.

  3. and different results for domain $( nk , nk+k )$ where $n=1,2,3.....p$ such that $p < b$.

and then sum all of these to get the answer.

hope this helped

$\endgroup$
  • $\begingroup$ here assumption is that a and b are greater than zero. $\endgroup$ – Jasser Sep 11 '14 at 6:22

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.