4
$\begingroup$

I need to find the smallest value of $x$ such that:

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

EDIT: where $0 < x < a < b$, and $x \in \mathbb{N}$

Is there a closed-form solution for this problem? Any help or suggestions are greatly appreciated.

Thanks.

$\endgroup$
  • 2
    $\begingroup$ hint: if $0<a<x<b$ the equality is invalid; but if $0<a<b<x$ the result is correct. $\endgroup$ – Hilario Fernandes Oct 15 '14 at 23:37
  • 2
    $\begingroup$ @HilarioFernandes But the inequality may be valid when $0<x<a<b$, for example, $x=3$, $a=6$, $b=7$. $\endgroup$ – user21467 Oct 16 '14 at 0:12
  • 2
    $\begingroup$ There is often no such smallest $x$; for example, $\lfloor\frac2x\rfloor < \lfloor\frac3x\rfloor$ if $0<x\le\frac32$ and $\lfloor\frac2x\rfloor = \lfloor\frac3x\rfloor$ if $\frac32<x\le2$. Do you want the infimum? Or do you want $\lceil\cdot\rceil$? $\endgroup$ – user21467 Oct 16 '14 at 15:10
  • 2
    $\begingroup$ @StevenTaschuk My problem was ill defined. In fact, $x \in \mathbb{N}$. $\endgroup$ – mandy Oct 16 '14 at 20:37
  • 3
    $\begingroup$ @WillJagy I wish it was an assignment! I am implementing a big data algorithm where I could really benefit from the speed-up of a closed form solution. So far, I iterate between $b-a+1<x<a-1$ but that's not viable for very large values of $a$ and $b$. $\endgroup$ – mandy Oct 17 '14 at 21:31
0
$\begingroup$

x = 1

a = 1/2

b = 3/4

These three values satisfy the equality.

$$\lfloor \frac ax \rfloor = \lfloor \frac bx \rfloor$$

Substituting in the values...

$$\lfloor \frac 12 \rfloor = \lfloor \frac 34 \rfloor$$

$$0 = 0$$

The smallest value for x is 1.

a and b can be any numbers in the range [n, n+1) where n is an integer so long as b > a. Their solution is infinite.

$\endgroup$

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.