Find particular pair of values that satisfy equation

Question

I think this is might be a fairly simple problem, but I can't for the life of me think of a way to approach it.

In this equation, for a given $x$ and $y$, with $x,y,a,b$ non-negative integers:

$x2^a + b = y$

Is there any analytical way to find the $2^a$ and $b$ that maximizes $2^a$, or an efficient algorithm?

Answer 1

Since $b$ is nonnegative, we must have $y - x 2^a \geq 0$, or $\frac{y}{x} \geq 2^a \geq 1$. (So this is a new problem instance constraint -- all valid instances have $y \geq x$.)

Since we want to maximize $a$, set $a = \lfloor \log_2(y/x) \rfloor$, where the "lower brackets" are the floor function. This is the largest permissible value of $a$. Then set $b = y - x 2^a$.

(Note that your bounds on $x$ and $y$, $\sim 2^{10}$, are not so small that it is faster to compute left shifts of $x$ and compare those with $y$ than it is to compute this logarithm. Nor are they so large that taking this logarithm is "expensive" enough to justify doing a crude search based on digit lengths to estimate the log before sharpening it with tricky precision preserving techniques.)

Answer 2

If $x = 0$, then $b = y$ ; if $x>y$, no solutions ; and else, take $a = \lfloor \log_2 \big( \frac{y}{x} \big) \rfloor$ and $b = y - x 2^a$ to maximise $2^a$.