Quote:
Originally Posted by Uncwilly
I can choose to subtract n2 from n and go right to the final in a single step. Or I can divide n by n (no cost division) and then add 1, thus a single step.

No  as stated, the moves that cost one are replace n with n+1 or n1, not nx. The no cost move is to replace n with n/d where d <= square root(n).
For the example given to demonstrate the process the factoring strategy works (but you'll have to write the divisions in reverse) because it's smooth and has 4 as a factor. You can't go from 106 to 2 because 53^2 > 106.
All powers of 2 are trivially 0 move numbers, and any 0 move number n multiplied by a number m where m < n results in another 0 move number.