4

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.

mandy
  • 41
  • 2
    hint: if $0<a<x<b$ the equality is invalid; but if $0<a<b<x$ the result is correct. – Hilario Fernandes Oct 15 '14 at 23:37
  • 2
    @HilarioFernandes But the inequality may be valid when $0<x<a<b$, for example, $x=3$, $a=6$, $b=7$. –  Oct 16 '14 at 00:12
  • What if $a < 0$ and $b > 0$? Doesn't that have no solution? – Bruce Zheng Oct 16 '14 at 00:22
  • @BruceZheng you're right, thank you! I've edited my problem statement accordingly – mandy Oct 16 '14 at 01:26
  • @WillJagy Indeed. I have re-edited to constrain $x$ such that $x<a$. The other cases are trivial. – mandy Oct 16 '14 at 01:48
  • I guess you search positive $x$, i.e. your constrain should be $0< x <a,;$ otherwise there is no smallest value (all negative $x$ with large enough $|x|$ are solutions). – gammatester Oct 16 '14 at 07:31
  • 2
    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$? –  Oct 16 '14 at 15:10
  • 2
    @StevenTaschuk My problem was ill defined. In fact, $x \in \mathbb{N}$. – mandy Oct 16 '14 at 20:37
  • You are asking for the smallest $x$ that satisfies the conditions (1) $x\in\mathbb{N}$ and (2) $\left\lfloor\frac{a}{x}\right\rfloor=\left\lfloor\frac{b}{x}\right\rfloor$. You are already asking to find the smallest $x$ satisfying (1) and (2). What does it add to include "$x<a$"? Either the smallest $x$ satisfying (1) and (2) will be less than $a$ or it won't. – 2'5 9'2 Oct 16 '14 at 21:09
  • Are you certain that $a$ and $b$ are not required to be integers? If it is known that $a$ and $b$ are integers, it would help a lot. – 2'5 9'2 Oct 16 '14 at 21:25
  • @alex.jordan Sorry, but I can't see how $a$ and $b$ being integers can help a lot. Can you please explain? – mandy Oct 17 '14 at 12:45
  • @alex.jordan I am specifying that $x < a$ because in the trivial case, when $b\ge 2a$, $x = b+1$. It's something I added after thinking about the implications of comments from Hilario Fernandez and Steven Taschuk. – mandy Oct 17 '14 at 12:52
  • If $a$ and $b$ are integers, then you could look into reverse engineering the conditions on $a$ and $b$ that would lead to $x$. And you could use residues mod $x$. For example, you could start off with: (1) $a=b\iff x=1$; (2) $(a,b)=(2k,2k+1)\iff x=2$; (3) $(a,b)\in{(6k,6k+2),(6k+1,6k+2),(6k+3,6k+4),(6k+3,6k+5)}\iff x=3$; You could try to describe the pattern that is appearing here. But this only works for integers. – 2'5 9'2 Oct 17 '14 at 17:15
  • The problem should be stated something like: for given $a<b$, what is the smallest $x\in\mathbb{N}$ such that $\left\lfloor\frac{a}{x}\right\rfloor=\left\lfloor\frac{b}{x}\right\rfloor$? What conditions on $a,b$ will make this smallest $x$ greater than $b$, and what conditions on $a,b$ will make this smallest $x$ smaller than $a$? The way it's all about finding an $x$ that is dependent on $a$ and $b$, and not about finding an $x$ that is dependent on $a$, $b$, and $x$. – 2'5 9'2 Oct 17 '14 at 17:18
  • 3
    @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$. – mandy Oct 17 '14 at 21:31
  • @WillJagy You can choose any to be bigger, I does not matter. – mandy Oct 18 '14 at 21:07
  • @mandy I suspect this could be done in $\sqrt{b}$ time, would that help? – Erick Wong Nov 04 '14 at 06:53

0 Answers0