# A peculiar algorithm

You are given an initial integer and a target integer. You may change the initial number by doing any of the operations $+2, -2, \times 2, \div 2$, any number of times in any order, to get the target number. For example, from $16$ to $40$, you may do $+2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2, +2$, or $\div 2, \div 2, +2, +2, +2, \times 2, \times 2$. The only restriction is that no intermediate operation may result on a fraction.

Is there a feasible algorithm (say, it takes $O(n \log n)$ time for a maximum absolute input of $n$) to find the shortest solution for a given pair of integers?

-
You can use $\TeX$ on this site by enclosing formulas in dollar signs; single dollar signs for inline formulas and double dollar signs for displayed equations. You can see the source code for any math formatting you see on this site by right-clicking on it and selecting "Show Math As:TeX Commands". Here's a basic tutorial and quick reference. There's an "edit" link under the question – joriki Sep 20 '12 at 10:30
One possible way is As follows: Think of a number as a binary sequence. According to the last digit, either div2 or times2, -2, div2 behaves as a binary right-shifting operation (which is usually denoted as >>). Thus we can shift the original input repeatedly to clear the input. Now similar trick allows us to mimic the left-shifting operator (<<) and increment operator(++), which allow us to 'build up' the target number. This is the farthest from what we regard as natural, but anyway it proves that we can find such a one. – Sangchul Lee Sep 20 '12 at 10:35
Finding the optimal result seems hard. The naive algorithm I imagine, prompted by sos440, would go from 12 to 21 by 12,6,3,1,2,4,8,10,20,40,42,21, but you can also do 12,6,4,8 and so on. – Ross Millikan Sep 20 '12 at 13:27
This is a shortest path problem in the graph with vertex set $V=\mathbb{N}$ and whose edges correspond to the allowed operations (i.e. 7 would be connected to 9, 5, and 14). You may be able to make an efficient algorithm out of this view by appropriately pruning the graph to have a finite (and small enough) number of vertices and then applying standard shortest path algorithms. At the moment I don't have time to think about the details. – Noah Stein Sep 20 '12 at 13:47

Consider the following algorithm which takes $m$ to $0$:

• Step 1: If $m=0$, exit.

• Step 2: If $m$ is even, $m \mapsto m \div 2$.

• Step 3: If $m$ is odd then

• If $m>0$ then, $m \mapsto 2m \mapsto 2m-2 \mapsto (2m-2)/2=m-1$.

• If $m<0$ then, $m \mapsto 2m \mapsto 2m+2 \mapsto (2m+2)/2=m+1$.

• Step 4: Goto Step 1.

This algorithm terminates in $O(\log |m|)$ steps (a strict upper bound would be $4 \log_2 |m|$).

We can similarly apply the above algorithm on the input $n$ instead, which will take $n$ to $0$ in $O(\log |n|)$ steps. Importantly, we can reverse the steps, and hence take $0$ to $n$ in $O(\log |n|)$ steps.

Hence we can get from $m$ to $n$ in $O(\log |mn|)$ steps. This will be asymptotically the best possible (up to a constant factor).

(Comment: if e.g. $m$ is negative and $n$ is positive, then we must go through at least one of $\{-1,0,1\}$ since multiplication by $2$ and division by $2$ does not affect sign.)

-