1
$\begingroup$

Increasing the integer $k$, I can make the floor of $L/k$ smaller than $r$:

$$\left\lfloor \frac{L}{k} \right\rfloor \lt r$$

where $L, k, r$ are positive integers, $k\leq \lfloor \frac{L}{2} \rfloor$.

Is it possible to write down a "closed form" (or whatever easily computable expression, possibly through low and upper bounds) for the first integer $k$ where the displayed inequality holds true ?

$\endgroup$
  • $\begingroup$ The maximum solution of $\frac{L}{K}$ lies in $[(r-1),r)$ $\endgroup$ – Mann May 13 '15 at 6:32
  • $\begingroup$ Computable is a strong word to use, you can certainly use bisection to determine the value. $\endgroup$ – Jared May 13 '15 at 6:58
4
$\begingroup$

We want the first $k$ with $\frac Lk<\lceil r\rceil$, which is the first $k$ with $\frac L{\lceil r\rceil }<k$, i.e., $$ k=1+\left\lfloor \frac L{\lceil r\rceil }\right\rfloor$$

Edit: I just see that $r$ is an integer, so my writing $\lceil r\rceil$ is unnecessarily cautious, we can simplify to $$ k=1+\left\lfloor \frac L{r}\right\rfloor,$$ but note that this is not the same as $\lceil \frac L r\rceil$ because $r$ may be a divisor of $L$.

$\endgroup$
  • $\begingroup$ Thank you Hagen, very nice. Is it obvious that $\left\lfloor \frac{L}{k} \right\rfloor \lt r$ is the same as $\frac Lk<\lceil r\rceil$ ? Is there a simple way to look at it and "see" that this is true? So in general every time I have $\lfloor x \rfloor < r$ I can just consider: $x<\lceil r\rceil$ ? $\endgroup$ – Pam May 13 '15 at 11:09
  • $\begingroup$ ...or do we need $r$ to be an integer at that very first step too ? $\endgroup$ – Pam May 13 '15 at 12:11
2
$\begingroup$

Note that as you increase $k$, $L/k$ decreases monotonically. Thus, the first value $k$ satisfying this inequality satisfies $$\left\lfloor \frac{L}{k}\right\rfloor <r\le\left\lfloor \frac{L}{k-1}\right\rfloor.$$ Now, since $r$ is a positive integer, this occurs iff $$ \frac{L}{k} <r\le \frac{L}{k-1}.$$ or equivalently $$\frac{L}{r}-1< k-1\le \frac{L}{r}.$$ Then since $k-1$ is a positive integer $$k-1=\left\lfloor\frac{L}{r}\right\rfloor,$$ so $$k=\left\lfloor\frac{L}{r}\right\rfloor+1.$$

$\endgroup$
  • $\begingroup$ I'm new to stackexchange, could the downvoter please explain their vote? $\endgroup$ – ApproximatelyTrue May 13 '15 at 6:41
  • $\begingroup$ Maybe because you get the wrong $k$ for example when $L=6$ and $r=3$ $\endgroup$ – Hagen von Eitzen May 13 '15 at 6:42
  • 1
    $\begingroup$ Ah, I see the problem. I'm editing my answer to correct it. Or is the appropriate action to delete it? $\endgroup$ – ApproximatelyTrue May 13 '15 at 6:48
  • $\begingroup$ Thank you. Pretty neat. The fact that r is an integer seems to be quite useful to obtain a nice solution. $\endgroup$ – Pam May 13 '15 at 12:09

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.