Challenge: Primitive Calculator

Problem

Primitive Calculator Problem

Find the minimum number of operations needed to get a positive integer $n$ from $1$ using only three operations: add $1$, multiply by $2$, and multiply by $3$.

Input: An integer $n$.

Output: The minimum number of operations “$+1$,” “$×2$,” and “$×3$” needed to get $n$ from 1.

You are given a calculator that only performs the following three operations with an integer $x$: add $1$ to $x$, multiply $x$ by $2$, or multiply $x$ by $3$. Given a positive integer $n$, your goal is to find the minimum number of operations needed to obtain $n$ starting from the number $1$. Before solving the programming challenge below, test your intuition with our Primitive Calculator puzzle.

Let’s try a greedy strategy for solving this problem. If the current number is at most $n/3$, multiply it by $3$. If it is larger than $n/3$, but at most $n/2$, multiply it by $2$. Otherwise add $1$ ...