Solving an equation that contains the floor function

[Arman777]

Let suppose I have three positive integers $a, b,c$ and one unknown $x$ ($x$ is also a positive integer). Solve for the smallest $x$ that satisfies this equation$$\left \lfloor\frac{x}{a} \right\rfloor + \left \lfloor \frac{x}{b} \right\rfloor \geq c$$

where $\lfloor x\rfloor$ is the [floor function][1]

For instance let $a = 1$, $b=1$ and $c=5$ in this case

$$\left \lfloor x \right\rfloor + \left \lfloor x \right\rfloor \geq 5$$

here the smallest $x$ is $3$.

For another case, if $a=3$ and $b=5$ and $c=4$ we obtain

$$\left \lfloor\frac{x}{3} \right\rfloor + \left \lfloor \frac{x}{5} \right\rfloor \geq 4$$

here the smallest $x$ is $9$

My question is, can we find the smallest $x$ exactly ?

[1]: https://en.wikipedia.org/wiki/Floor_and_ceiling_functions

 

[mfb]

My question is, can we find the smallest $x$ exactly ?

Sure, you provided two examples already. There is only a finite number of values to consider and it's trivial to check if a given x is the solution, so obviously we can always find the smallest x.

Without rounding and without limiting the solution to integers, you would get x=c/(1/a+1/b). If you round that down and plug it into the original expression then the left side will be at most 4 smaller than c and it will be at most c (you can probably do a more refined analysis and set a tighter lower limit).

The terms on the left side only increase if x is a multiple of a and b, so you can go up in the multiples of these until the left side reaches c.
That's a constant time algorithm to find the smallest x.

 

[anuttarasammyak]

By the relataion
$$x\ mod\ a=x-a\lfloor \frac{x}{a} \rfloor$$
We can rewrite the equation as
$$x \geq \frac{a(x\ mod\ b)+b(x\ mod\ a)+abc}{a+b}...(1)$$
As for RHS of the equation
$$\frac{abc}{a+b}\leq RHS \leq \frac{a(b-1)+b(a-1)+abc}{a+b}$$
We get rough estimation of x.

For examples of OP
For a=1,b=1,c=5
$$\frac{5}{2} \leq RHS \leq \frac{5}{2}$$
$x_{min}=3$

For a=3, b=5,c=4
$$7.\ ..\leq RHS \leq 10.\ ..$$
Candidates of $x_{min}=\{8,9,10,11\}$. From the smallest number 8, we start checking whether it satisfies (1) , if not stepping the number up, to find $x_{min}=9$. The procedure is easily programmable.

 

[anuttarasammyak]

$$f(x):=\lfloor \frac{x}{a} \rfloor +\lfloor \frac{x}{b} \rfloor -c$$
f(x) increases with x. We may state the equation
$$f(x-1)f(x) \leq 0$$
where
$$f(x-1)\neq 0, <0$$

 

[mfb]

@anuttarasammyak: How does that rewriting help?

 

[anuttarasammyak]

The merit is to get unique solution in comparison with multiple candidates as mentioned in my post #3. f(x) is the smallest plus means f(x-1) is minus. I admit it becomes more complicated equation.

 

[mfb]

I don't see the advantage over saying "the smallest one" like in post 1. It's just "the smallest one" put into an equation that you still need to evaluate for every x to find the smallest one.

x must be a multiple of a or b, that's helping a lot for larger a,b. In your second example in post 3, only 9 and 10 are candidates that need to be checked.

 

[anuttarasammyak]

f(x) defined in #4 is monotonous increasing function. If we find a solution $x_0$ of
$f(x)f(x-1) \leq 0$, is it enough to pay attention not to every x but x around $x_0$, e.g.
$[x_0- max[a,b],x_0+ max[a,b]]$ ?

ex. a=b=100,c=2
$f(1)=f(2)=...=f(99)=-2$
$f(100)=f(101)=...=f(199)=0$, 100 smallest solutions.

 

[mfb]

You are still trying different x in some range just as before.

x/a or x/b will be an integer at the minimal x and [x/a]+[x/b] can only increase by 0,1 or 2 when we increase x by 1. That means $c \leq \frac x a + \frac x b \leq c+1$. This is a better restriction on the range. $\frac{c}{1/a+1/b} \leq x \leq \frac{c+1}{1/a+1/b}$.

Let's get rid of double fractions:
$\frac{abc}{a+b} \leq x \leq \frac{ab(c+1)}{a+b} = \frac{abc}{a+b} + \frac{ab}{a+b}$
If x is a multiple of a, then write x=ka and divide everything by a:
$\frac{bc}{a+b} \leq k \leq \frac{bc}{a+b} + \frac{b}{a+b}$
As $\frac{b}{a+b}$ is smaller than 1 we only need to investigate a single element (a single multiple of a).
If x is a multiple of b, then write x=lb and divide everything by b:
$\frac{ac}{a+b} \leq l \leq \frac{ac}{a+b} + \frac{a}{a+b}$
As $\frac{a}{a+b}$ is smaller than 1 we only need to investigate a single element (a single multiple of b).

That's two elements to study as possible smallest x. And we have direct formulas to get these two elements as integers between (in general) non-integer boundaries. That's all we need.

Edit: These elements need to be the largest integers smaller than or matching the upper bound.

$$x_1 = a \lfloor \frac{b(c+1)}{a+b}\rfloor$$
$$x_2 = b \lfloor \frac{a(c+1)}{a+b}\rfloor$$
One of these two will be the answer.

 

[anuttarasammyak]

I see. I say x that f(x) takes the smallest positive value. You say the smallest x that f(x)>0. Since f(x) is monotonous function they are different only in degeneration. In the case of #8 I have 100 solutions and you have only one x=100. The equation of #4 together with $f(x-1)\neq0$ gives the solution you say.

The equation requires
$$x \mod a = 0$$ or $$x \mod b=0$$
Say $x \mod a =0$ and $x=na$
$$c \leq n+\lfloor \frac{na}{b} \rfloor < c+1$$
$$\lfloor n+\frac{na}{b} \rfloor =c$$
$$\frac{c}{1+\frac{a}{b}} \leq n < \frac{c+1}{1+\frac{a}{b}}$$
For positive n to exist
$$1+\frac{a}{b}\leq c$$
Only one integer is allowed in the region since $\frac{1} {1+\frac{a}{b}}<1$,
$$n=\lfloor \frac{c+1}{1+\frac{a}{b}} \rfloor$$
$$x=a\lfloor \frac{c+1}{1+\frac{a}{b}} \rfloor$$

Let $a \leq b,r=\frac{b}{a} \geq 1$.
we get the solution:
For $c<\frac{b}{a}$, $$a\lfloor \frac{c+1}{1+\frac{a}{b}} \rfloor$$
For $\frac{b}{a}\leq c$
$$\min [a\lfloor \frac{c+1}{1+\frac{a}{b}} \rfloor, b\lfloor \frac{c+1}{1+\frac{b}{a}} \rfloor ] =b\lfloor \frac{c+1}{1+\frac{b}{a}} \rfloor$$
Because
$$a\lfloor \frac{c+1}{1+\frac{a}{b}} \rfloor = a\lfloor \frac{r(c+1)}{1+r} \rfloor \geq ar\lfloor \frac{(c+1)}{1+r} \rfloor =b\lfloor \frac{c+1}{1+\frac{b}{a}} \rfloor$$