2
$\begingroup$

Came across this math problem while programming something:

Given positive $y$, $a$, and $b$, find an integer $x$, $a\lt x\lt b$, so that $y\bmod x$ (the remainder of $y$ when divided by $x$) is positive and less than or equal to $100$, $$0 \lt y\bmod x \leq 100.$$

I know sometimes it's not solvable depending on $y$ and the range. I'm not really sure where to begin because I wasn't very good at modular algebra.

I really don't want to have to try every possible number for $x$ between $a$ and $b$ because the range I'm using it for has over 25 million in length.

Edit: Sorry the question wasn't very clear. $y$, $a$, and $b$ are given. And I'm trying to find an $x$ that satisfies those conditions.

Edit 2: I've realize $y \bmod x$ need to be less than or equal to $100$ and also over $0$.

$\endgroup$
  • 3
    $\begingroup$ What's the actual question? $\endgroup$ – Robin Chapman Nov 26 '10 at 14:06
  • $\begingroup$ Is the question: find $x\in[a,b]$ such that $y \mod x \le 100$ ? $\endgroup$ – Frédéric Grosshans Nov 26 '10 at 15:55
1
$\begingroup$

I'm not sure I understood your question. Let's suppose your question is the following :

Let $100=c<a<b<y$ be 4 given integers, how to find $x$ such that $$ a\le x \le b \text{ and } y \mod x \le c $$

Here is a tentative algorithm, which is probably not optimal, but (slightly) better that trying all the possible values for $x$.

First, try the first possibility $x=a$ and perform an euclidean division to find $q$ and $r$ such that $y=qa+r$.

  • if $0<r\le c$, $x=a$ and you're done
  • otherwise, divide $r$ by $q$ to find $k,l$ such that $r=kq+l$.
    • if $0<l\le c$, $x=a+k$ is your solution if it is in $[a,b]$. If not, try $b$. If $b$ is not a solution either, then tere is no solution.
    • otherwise, increase $a$ by $k+1$ and start again from the beginning.

Of course, you stop repeating the above as soon as $a$ becomes bigger than $b$, which would mean that ther is no solution.

Edit to take into account the $0 < y \mod c$ condition

I don't think this condition change the search much, at least if you use the above algorithm. Hoxever, if you have a $z$ such that $y \mod z =0$, you can write $y=mz$, which might be helpful. For example, if $m\le c$, $x=z+1$ will be a solution.

Edit to correct for the $a+k>b$ case Edit To be more clear, the algorithm above find $k,q,l$ such that $y=(a+k)q+l$, and tries to get $l$ as small as possible (without trying too much)

$\endgroup$
  • $\begingroup$ Sorry I overlooked something in my question. y mod x needs to be less than 100 and over 0. $\endgroup$ – fent Nov 26 '10 at 17:30
  • $\begingroup$ This algorithm doesn't work with $c = 100, a = 400, b = 505, y = 1520$. It gives me 506 as the answer which is out of the range. $\endgroup$ – fent Nov 27 '10 at 7:29
  • $\begingroup$ OK I see the problem : I forgot to check the condition on b when trying do reduce the modulus. 505 is a solution. Actually, every integer between 474 and 505 are solutions. Do you need all the solutions, the smallest solution or any solution ? $\endgroup$ – Frédéric Grosshans Nov 27 '10 at 18:43
  • $\begingroup$ The smallest solution would be better, since it would mean that $y mod x$ is the closest to $c$ $\endgroup$ – fent Nov 28 '10 at 2:59
  • $\begingroup$ OK, I've looked for the one with the smallest $y mod x$. To have a bigger modulus, you need to decrease $k$. $\endgroup$ – Frédéric Grosshans Nov 28 '10 at 20:57
0
$\begingroup$

Your question is equivalent to asking whether any element of {y-1, y-2, $\ldots$, y-100} has a divisor in the range (a,b). So if you can factor all the 100 numbers, you can check that. Unfortunately, factoring is pretty hard and then you have the NP complete knapsack problem to solve in looking through all the factors for one that is in range.

$\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.