5

The problem is

Given a positive integer $n$, what is the minimum number of operations to make the number 1. There are 3 options to choose from (1) if the number is even you can divide by 2. (2) for any number you can add 1. (3) for any number you can subtract 1

So for example, the minimum number of operations to make $15$ become $1$ is the following path:

$$ 15 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1 $$

another example

$$ 13 \rightarrow 12 \rightarrow 6 \rightarrow 3 \rightarrow 2 \rightarrow 1 $$

It's pretty obvious to me that for any number, if it is even, we should divide by 2 immediately instead of adding or subtracting 1.

What is not obvious to me is that apparently, the optimal solution is such that if you have an odd number, you should either add 1 or subtract 1, depending on which operation gets you to a number that is divisible by 4. So based on this, if we had a number like $21$, we would want to subtract 1 and get to 20 instead of adding 1 and getting to 22 because $20$ is divisible by 4.

Can someone explain to me why the optimal trajectory is to choose the increment/decrement that gets you to a multiple of 4? I also understand that for any given odd number, adding or subtracting will make the resulting number divisible by 2, but exactly 1 such choice will make the number divisible by 4.

Edit 1: Is the intuition of wanting divisibility by 4 because for any number is divisible by 4, we can divide by 2 two times, and for any number that is not divisible by 4, then we can only divide by 2 one time and the resulting number is odd.

24n8
  • 1,455
  • I think it is quite difficult to find the best strategy in general. Maybe, we have to begin with the "bad choice" to arrive at a larger power of $2$ faster. Interesting question however (+1) – Peter Sep 29 '20 at 19:01
  • @Peter I should add that this is actually a programming question, specifically one that can be solved with dynamic programming. But the reason I posted is I don't understand this mathematical intuition. – 24n8 Sep 29 '20 at 19:02
  • Be careful when trying to phrase this for a formal proof since 3->2->1 is faster than 3->4->2->1. I would consider attempting to use strong-induction here. – JMoravitz Sep 29 '20 at 19:02
  • @JMoravitz right, I wasn't trying to imply that the $15->16->...$ case applied in general -- I was just picking out an example where the optimal solution comes with adding because one might be greedy and think "oh let me just keep dividing or subtracting and that should get me the optimal solution" – 24n8 Sep 29 '20 at 19:04
  • Consider this... the number you start with written in binary. Consider the "current score" of the number to be the number of $1$'s plus the number of digits. The action of subtracting $1$ from an odd number will decrease the score by exactly $1$. The action of dividing by $2$ will also decrease the score by exactly $1$. The action of adding $1$ to an odd number will not change the score in the event that the second to last digit is $0$ (as it goes from $xxxx01$ to $xxxx10$) or it will decrease the score by at least two (as it goes from $xx01\dots 11$ to $xx10\dots 00$) except for $3$ – JMoravitz Sep 29 '20 at 19:13
  • A greedy algorithm attempting to decrease our score to $2$ (our number having become the number $1$) the fastest by making whatever decision is best at the time is what you are proposing. It should be clear that the path which uses these $+1$'s decreasing our score by more than one more efficiently will be best. What remains is to show that foregoing that decrease by more than one at an earlier step can't lead to more or more effective decreases by more than one at later steps than would otherwise have been possible. – JMoravitz Sep 29 '20 at 19:15
  • There is an algorithm described on Stack Overflow which claims to be optimal: https://stackoverflow.com/a/39589499/1187415. – Martin R Sep 29 '20 at 19:24
  • this is the powermod algorithm; the $x+1$ operation is not required; it is a touch faster if some point in the chain is of the form $2^w - 1,$ as in the example $15.$ In any case the number of operations is approximately $\log_2 n$ – Will Jagy Sep 29 '20 at 19:39
  • @JMoravitz I think I follow your logic, but how can "What remains is to show that foregoing that decrease by more than one at an earlier step can't lead to more or more effective decreases by more than one at later steps than would otherwise have been possible." be shown in the general sense? – 24n8 Sep 29 '20 at 19:40
  • https://en.wikipedia.org/wiki/Modular_exponentiation – Will Jagy Sep 29 '20 at 19:41

1 Answers1

1

Your intuition is right (except for $n=3$). You want to be able to divide by $2$ as many times as possible.

Let $f(n)$ be the minimum number of operations to get to $1$. Given $n = 4k+1$, you have two choices: To add $1$ then divide by $2$ to make it $2k+1$ (2 steps) or to subtract $1$ then divide by $2$ twice to make it $k$ (3 steps). In a similar way, for $2k+1$, you have two options: to make it $k$ (which is clearly pointless) or $k+1$ (which both take two steps). This means that for adding $1$ to be a better choice than subtracting $1$, $f(k+1)+4 < f(k)+3$ or equivalently $f(k+1) + 1 < f(k)$ must be true. But this is impossible since $f(k)$ and $f(k+1)$ differ by at most $1$. This only shows that subtracting $1$ is as good or better than adding $1$, not necessarily better (which is not the case with $n = 29$ for example).

Similarly, if $n = 4k-1$, you can make it $k$ by adding $1$ (3 steps) or $2k-1$ by subtracting $1$ (2 steps). If $k = 1$, then $2k-1$ is already $1$, so $f(3) = 2$ is a special case. Following in a similar way to the $n = 4k+1$ case, for subtracting $1$ to be a better choice than adding $1$, $f(k-1)+1<f(k)$ must be true. But this is impossible since $f(k-1)$ and $f(k)$ differ by at most $1$. This only shows that adding $1$ is as good or better than subtracting $1$, not necessarily better (which is not the case with $n=27$ for example).

This means that $f(4k-1) = 3+f(k)$, $f(4k+1) = 3+f(k)$, and you already found that $f(2k) = 1+f(k)$.

Varun Vejalla
  • 8,873