The M2S3 Game

The M2S3 game is a simple arithmetic puzzle. Given two numbers, the task is how to get from one number to the next using only multiplication by two (M2) and subtraction of three (S3). The goal is to minimize the number of steps.

In the M2S3 game, a sequence $\sigma$ consists of a list of zero, one, or more operations, each of which is either $\times 2$ or $-3$. The sequence can be applied to any sufficiently large positive integer $x$ by performing the operations in the given order; we will write $\sigma(x)$ for the outcome, which is necessarily also a positive integer. $($If any of the steps in calculating $\sigma(x)$ yields a non-positive value, we will declare $\sigma(x)$ undefined.$)$

A concrete M2S3 puzzle is as follows: given an initial value $x$, find the sequence that leads to a given outcome $y$ in a minimum number of steps; that is, for which sequence $\sigma$ of minimum length is $\sigma(x) = y$?

We will call the answer to this puzzle $\Sigma(x,y)$.

An example of a sequence is $\sigma = [-3, -3, \times 2, \times 2, -3, \times 2, -3, \times 2].$ When applied to the initial value $x = 13$, the sequence generates the output $\sigma(13) = 94$. The detailed steps are as follows: $13 \to 10 \to 7 \to 14 \to 28 \to 25 \to 50 \to 47 \to 94.$

The sequence $\sigma$ cannot be applied if $x$ is too small. What is the minimum value of $x$ for which $\sigma(x)$ is defined?

---

If $x < 7$, the first or second subtraction results in zero, which is not allowed. If $x = 7$, things go fine at first but break down toward the end: $7 \to 4 \to 1 \to 2 \to 4 \to 1 \to 2 \to -1\ !!$ The smallest value for which $\sigma(x)$ is defined is $x = 8$: $8 \to 5 \to 2 \to 4 \to 8 \to 5 \to 10 \to 7 \to 14.\ _\square$

Challenges:

1. Prove that if $\sigma(x_0)$ is defined, then $\sigma(x)$ is defined for all $x > x_0$, and that in fact $\sigma(x) > \sigma(x_0)$.
2. Find a general rule to determine the minimum value of $x$ for which $\sigma(x)$ is defined.

Find the M2S3 sequence of minimum length from 8 to 11.

---

The answer is $\Sigma(8,11) = [-3, \times 2, -3, \times 2, -3]$; the steps are $8 \to 5 \to 10 \to 7 \to 14 \to 11.\ _\square$

There are several strategies to find this answer:

1. Start with $x = 8$ and apply both of the possible operators. Do the same for the results, and so on. As soon as the outcome is 11, the search is complete, and the solution is guaranteed to be minimal. This solution is illustrated below. The dashed boxes indicate numbers that occurred in an earlier stage of the process, and therefore need not to be explored because it would only lead to longer-than-minimal sequences.

2. Start with $y = 11$ and work backward. The inverse operation $+3$ can be applied to each number, but the inverse operation $\div 2$ only applies to even numbers. This method is more efficient than the first, because fewer attempts are needed.

3. Instead of exhaustive searching as in 1 and 2 above, one can also calculate the solution. This will be discussed in the sections below.

Is there a way to determine whether a solution $\Sigma(x,y)$ exists and what that solution is, without exhaustive search?

Arithmetic modulo 3 gives some interesting insights. The positive numbers can be sorted into three bins: multiples of three, one less than multiples of three, and one more than multiples of three. Thus we will write $\begin{cases} x \equiv 0 & \text{if}\ x = 3n, \\ x \equiv -1 & \text{if}\ x = 3n-1, \\ x \equiv 1 & \text{if}\ x = 3n+1. \end{cases}$ Now consider the effect of the operations on these bins:

• Subtracting three results in a number from the same bin. In other words, $x - 3 \equiv x$.
• Multiplication by two has the same effect as flipping the sign: $x \times 2 \equiv -x$.

Therefore, if we begin with a multiple of three $(x \equiv 0),$ the same will be true for every next number in the calculation. If we begin with any other number ($x \equiv \pm 1$), the same will remain true; only the multiplication by two will swap back and forth between the $+1$ and $-1$ bins. This leads to the following conclusions:

1. If $x$ is a multiple of 3, but $y$ is not, then there is no solution to the M2S3 game. Likewise, if $y$ is a multiple of 3, but $x$ is not, there is no solution.
2. If $x$ and $y$ are both multiples of 3, all intermediate values in the calculation are multiples of 3. We might as well divide everything by three, and play a reduced game M2S1, where we subtract one instead of three. For instance, $12 \to 24 \to 21 \to 18 \to 36 \to 33\ \ \ \ \ \text{becomes}\ \ \ \ \ 4 \to 8 \to 7 \to 6 \to 12 \to 11.$
3. If $x$ and $y$ are not multiples of 3, but belong to the same bin $(x \equiv y),$ then any sequence $\sigma(x) = y$ must contain an even number of multiplications by two. Likewise, if $x$ and $y$ are not multiples of 3, but belong to opposite bins $(x \equiv -y),$ then any sequence $\sigma(x) = y$ must contain an odd number of multiplications by two.

As long as either both or neither of $x$ and $y$ are multiples of three, a solution $\Sigma(x,y)$ is guaranteed to exist. We prove this by generating a sequence such that $\sigma(x) = y$; it is usually not the minimal sequence, but if one such sequence exists, there must be a minimal one as well.

The idea is first to multiply by two as much as necessary to make the number big enough, and then to subtract three until the desired value is reached.

Step A. Choose a number $n$ such that $2^n x > y$, and moreover,

• if $x,y$ are not multiples of three, $n$ should be even if $x \equiv y$ and odd if $x \not\equiv y$;

• if $x,y$ are multiples of three, no further conditions apply.

Step B. Generate the sequence $\sigma = [ \underbrace{\times 2, \times 2, \dots, \times 2}_{n\ \text{times}}, \underbrace{-3, -3, \dots, -3}_{p\ \text{times}} ],$ where $p = \frac{2^n x - y}3.$

Exercise: Prove that $\sigma(x) = y$ for this sequence.

We will call the smallest value of $n$ that satisfies the above conditions $\tilde n(x,y)$.

Let $x = 11$ and $y = 25$. Since $x \equiv -1$ and $y \equiv 1$ modulo 3, we need an odd value of $n$.

Since $2^1\cdot 11 = 22 < 25$ but $2^33\cdot 11 = 88 > 25$, the minimum allowed value is $n = \tilde n(11,25) = 3$. Then $p = \frac{2^3\cdot 11 - 25}3 = 21,$ so we define $\sigma = [ \times 2, \times 2, \times 2, \underbrace{-3, -3, \dots, -3}_{21\ \text{times}} ],$ and get the steps $11 \to 22 \to 44 \to 88 \to 85 \to 82 \to 79 \to \cdots \to 37 \to 34 \to 31 \to 28 \to 25.$ The number of steps in this sequence is $n + p = 24$, which is not minimal; but at least we have proven that a solution exists.

Exercise: Suppose we play the game M4S5, with the operations $\times 4$ and $-5$. Under what conditions does a sequence $\sigma(x,y)$ exist?

In the previous section we ended up with many subtractions at the end of the sequence. The number of subtractions may be reduced by placing them earlier in the sequence. The idea is that any subsequent multiplication by two "amplifies" the subtraction: $x\cdot 2\cdot 2\cdot 2 - 3 = 8x - 3,\ \ \ \text{but}\ \ \ (x\cdot 2-3)\cdot 2\cdot 2 = 8x - 12.$

More specifically, we can shorten a sequence by repeatedly replacing $[\dots, \times 2, -3, -3, \dots]\ \ \ \text{with}\ \ \ [\dots, -3, \times 2, \dots].$

We can repeat this process until no two successive subtractions remain, except possibly at the beginning of the sequence. Thus we find a sequence of the form $\sigma = [\underbrace{-3, -3, \dots, -3}_{q\ \text{times}}, \times 2, (-3), \times 2, (-3), \dots, \times 2, (-3)].$ Here the brackets $(-3)$ indicate that this step is optional.

The sequence contains $n$ multiplications by two. Let us number them from right to left, from $k = 0$ on the right to $k = n-1$ on the left. Define $r_k = \begin{cases} 0 & \text{if multiplication}\ n\ \text{is not immediately followed by a subtraction}, \\ 1 & \text{if multiplication}\ n \text{ is immediately followed by a subtraction}. \end{cases}$ The numbers $r_k$ may be interpreted as bits--digits in a binary numeral $r$. We have $r = \sum_{k=0}^{n-1} r_k 2^k,\ \ \ p = 2^n q + r.$ Here, $p$ is the "effective" number of subtractions of three, as defined above.

Challenge: Convince yourself that this formula for $p$ is correct.

We now have a sequence starting with $q$ subtractions, containing $n$ multiplications, and inserting $\#r = \sum r_k$ subtractions after the multiplications. (I will write $\#r$ for the number of ones in the binary representation of $r$.) Thus the sequence has length $\ell(\sigma) = n + q + \#r.$ Since we have minimized the number of subtractions, this sequence is guaranteed to be the shortest for the chosen value of multiplications, $n$. We will call the sequence generated this way $\Sigma(x,y,n)$.

Let $x = 16$ and $y = 142$. Then $x \equiv y \equiv 1$, so that we need an even number of multiplications $n$. Let us choose $n = 6$. $($Note that $\tilde n(x,y) = 4$ in this case; we do not pick the minimal value for $n.)$

Then $p = \frac{2^6\cdot 16 - 142}{3} = 294,$ so that we could in principle start with 6 multiplications and then apply 294 subtractions. The number of subtractions can be minimized by noting that $294 = 4\cdot 2^6 + 38\implies q = 4, r = 38.$ Writing $r = 38$ in binary notation, we get $\overline{r_5r_4r_3r_2r_1r_0} = 100110$. We now have a recipe for a sequence: start with $q = 4$ subtractions, then $n = 6$ multiplications, and insert one subtraction after multiplications 1, 2, and 5 (counting from the right and starting with zero). Thus, $\sigma = [-3, -3, -3, -3, \times 2, -3, \times 2, \times 2, \times 2, -3, \times 2, -3, \times 2].$ This corresponds to the calculation $16 \to 13 \to 10 \to 7 \to 4 \to 8 \to 5 \to 10 \to 20 \to 40 \to 37 \to 74 \to 71 \to 142.$ The length of this sequence is $n + q + \#r = 6 + 4 + 3 = 13$. It is obvious that this is not the shortest sequence; note that the calculation contains a cycle $\dots \to 10 \to \dots \to 10 \to \dots$.

Exercise: Repeat this calculation with the minimal number of multiplications $n = 4$. How does the sequence you find compare to the one with $n = 6$?

For a complete solution of the M2S3 puzzle, all that remains is to determine the value of $n$ for which $\Sigma(x,y,n)$ is minimal. It is tempting to conclude immediately that this happens for the minimal possible value $n = \tilde n(x,y)$; that is, $\Sigma(x,y) = \Sigma(x,y,\tilde n)$. But this must be proven first.

Can you prove this?

Conjecture: If a sequence $\sigma(x) = y$ has $n$ multiplications, and $n > \tilde n = \tilde n(x,y)$, then it contains at least one cycle. Removing the longest cycle will remove precisely $n - \tilde n$ multiplications, and will result in the shortest possible sequence.

In the previous example, the cycle was $\dots \to 10 \to 7 \to 4 \to 8 \to 5 \to 10 \to \dots$, consisting of two multiplications. Indeed, we generated this sequence with $n = 6$ while $\tilde n = 4$.