Solving an inequality with multiple floor terms

Question

Find the smallest $x$ that satisfies the inequality

$$ \left\lfloor \frac xa \right\rfloor\left\lfloor \frac xb \right\rfloor \geq y $$

where $x$, $y$, $a$, $b$ are natural numbers.

I need to solve that as part of a specific algorithm and the only thing I came up with so far is trying a lot of values for $x$. I am not sure if it can be solved analytically.

I am currently trying to find a lower bound for $x$ so that I don't have to try so many values. If I substitute $a$ and $b$ with their lowest possible value of $1$ it is clear that $x \geq \left\lfloor\sqrt{y}\right\rfloor$. That is still pretty conservative though, especially for large values of $a$ and $b$.

Is it possible to have a better lower bound or even an analytical solution for $x$?

---

Edit:

I realized that removing the floors can only increase the value of the left-hand side. And because the value needs to be larger, this can be used to directly solve for an $x$ that can not be too large already. (That was pointed out in the comments as well). If you solve that, you get $x \geq \left\lfloor\sqrt{aby}\right\rfloor$.

This is better than my previous lower bound. I have tested it algorithmically for values from 1 to 100 and it underestimates the $x$ by about 9% on average. There is however a worst-case, if $y$ and either $a$ or $b$ are 1 and the other $a$ or $b$ is very large.

Answer 1

We have: $$0 \leq \frac{x}{a}-\left\lfloor \frac xa \right\rfloor \leq \frac{a-1}{a}$$ with the maximum value of the difference happening when: $$x \mod{a} = a-1$$ From this we can set both lower and upper bounds. When we minimize the difference we get $$\frac{x}{a}\frac{x}{b} \geq y$$ giving us a lower bound of $x \geq \sqrt{yab}$. As $x$ is the smallest, $x-1$ should satisfy the equation

$$\left\lfloor \frac {x-1}a \right\rfloor\left\lfloor \frac {x-1}b \right\rfloor < y$$ Combining with our inequalities we get:

$$(\frac{x-1}{a}-\frac{a-1}{a}) (\frac{x-1}{b}-\frac{b-1}{b})< y \\ \Rightarrow (\frac{x}{a}-1) (\frac{x}{b}-1)< y\\ \Rightarrow (x-a) (x-b)< yab$$

This is a more complicated equation to solve, but it gives us the upper bound:

$$x < \sqrt{yab + \frac{(a-b)^2}{4}}+ \frac{a+b}{2} $$

Now that we have an upper bound and a lower bound, we need to find the value of $x$ quickly. We can do so using a divide and conquer algorithm.

We need three variables: $l$, who's initial value is set to the floor of the lower bound, $u$, who's initial value is set to the ceiling of the upper bound, and a third variable $n$. A number $n$ is "too high" if both $n$ and $n-1$ satisfy the $$f(x) = (\left\lfloor \frac xa \right\rfloor\left\lfloor \frac xb \right\rfloor \geq y)$$ equation. A number $n$ is "too low" if neither $n$ nor $n-1$ satisfy the above equation. A number $n$ is "just right" if $n$ satisfies the equation but $n-1$ does not. It is the number $x$ we are looking for. Our algorithm is as follows:

Check if either $u$ or $l$ is just right. If either is, we found $x$ and are done. If neither is:

$(1)$ set $n = \lfloor \frac{u+l}{2} \rfloor$. If $n$ is just right, we are done, $x = n$. If it is too high, set $u = n$ and goto step $(1)$. If it is too low, set $l = n$ and goto step $(1)$.

This should converge to $x$ with a runtime equal to the logarithm of the difference between the upper and lower bounds. $O(\ln(a+b))$ is a good aproximation.