Find minimum moves to transform one number to another

Question

Suppose we are given two positive integers, $a$ and $b$. Each move we are allowed to divide $a$ by 2 (but only if $a$ is even), multiply $a$ by 2, or add 1 to $a$. How many moves does it take to change $a$ to $b$? Find either a direct formula or an efficient algorithm for this.

Some progress that I have made: We can think of it as writing $b=2^ka+\text{something}$, where this "something" can be expressed by the sum of powers of 2 (including negative exponents). Clearly we'd want to choose $k$ so that $k$ is a large as possible while maintaining $2^ka<b$, and we'd want $k$ to be the total difference between the $\times 2$s and the $\div 2$s. However I'm not too sure how to go from here. Does someone have solution?

Answer 1

Hint:

Represent both numbers in binary. Your objective is to match the binary "patern". In one step you may:

• Remove $0$ from the end of $a$
• Add $0$ to the end of $a$
• Convert $0$ at the end of $a$ into $1$

Try to do by hand for some small numbers first e.g. $a=6$ and $b=17$