2
$\begingroup$

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?

  • 0
    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](http://meta.math.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference)'s a basic tutorial and quick reference. There's an "edit" link under the question2012-09-20
  • 0
    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.2012-09-20
  • 1
    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.2012-09-20
  • 1
    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.2012-09-20

1 Answers 1

2

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.)