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$ ...