Getting to 1653

The minimum number of operations can be solved by the following recursion relation:

• $A(0) = 0$
• $A(n) = 1 + min(A(n-1);f_2(n);f_3(n))$ for $n>0$

Where $f_i(n) = \frac{n}{i}$ if $n$ divides by $i$ , $\infty$ otherwise

This is because there are at most three ways to get to $n$ :

• from $n-1$
• from $n/3$ (if $n$ divides by $3$ )
• from $n/2$ (if $n$ divides by $2$ ).

Solving, $A(1653) = \boxed{12}$

One such minimal set of operations to give you $1653$ is the following:

$+1 \rightarrow \times 3 \rightarrow \times 3 \rightarrow +1 \rightarrow \times 2 \rightarrow \times 3 \rightarrow +1 \rightarrow \times 3 \rightarrow \times 3 \rightarrow +1 \rightarrow +1 \rightarrow \times 3$

And I know that @Pi Han Goh is going to want me to find a simpler solution that doesn't involve recursion like this, and, yes, I'll think about that, but for now this is the best I got! :-P