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