Solution: Primitive Calculator

Solution

Let $calculator(n)$ be the minimum number of operations needed to get $n$ from $1$. Since the last operation in an optimum sequence of operations is “$+1$,” “$×2$,” or “$×3$,” we get the following recurrence relation, for $n ≥ 1$:

$$calculator(n) = 1 + min \begin{cases} calculator(n-1) \\ calculator(n/2) & \text{if }~~ n~~ \text{is divisible by}~~ 2, \\ calculator(n/3) & \text{if }~~ n~~ \text{is divisible by}~~ 3. \end{cases}$$

This recurrence relation, together with the base case $calculator(1) = 1$, can be mechanically converted into a recursive and then an iterative algorithm.

---

 $Calculator(n)$:
 $table[1..n] ← [+∞, . . . , +∞]$
 $table[1] ← 0$
 for $k$ from $2$ to $n$:
 $table[k] = 1 + table[k − 1]$
 if $n$ is divisible by $2$:
  $table[k]=min(table[k],1+table[k/2])$
 if $n$ is divisible by $3$:
  $table[k]=min(table[k],1+table[k/3])$
 return $table[n]$

---

Recall, however, that besides the optimum value, we are asked to output an optimum sequence of operations. To do this, notice that we can find the last operation as follows:

• it is “$+1$,” if $calculator(n)=1+calculator(n−1)$;
• it is “$×2$,” if $n$ is divisible by $2$ and $calculator(n) = 1 + calculator(n/ 2)$;
• it is “$×3$,” if $n$ is divisible by $3$ and $calculator(n) = 1 + calculator(n/ 3)$.