Minimum number of operations (divide by 2/3 or subtract 1) to reduce $n$ to $1$ This question is inspired by a Stack Overflow question which involves the task to find an algorithm to solve the following problem:

Given a natural number $n$, what is the least number of moves you need to reduce it to $1$? Valid moves are:

*

*subtract $1$

*divide by $2$, applicable if $n \equiv 0 \pmod{2}$

*divide by $3$, applicable if $n \equiv 0 \pmod{3}$

For example, you can reduce 10 in 3 steps: $10 \rightarrow^{-1} 9 \rightarrow^{/3} 3 \rightarrow^{/3} 1$.
Let's define $f(n)$ as the answer for number $n$. Then we have $f(1) = 0$ and for $n > 1$:
$f(n) = 1 + \min \{ f(n-1), (n \mod 2) + f(\lfloor\frac{n}{2}\rfloor), (n\mod 3) + f(\lfloor\frac{n}{3}\rfloor) \}$
$n$ is restricted to $10^9$ in the original source, which makes it easy to solve in $O(n)$ using dynamic programming or a breadth-first search, but that isn't really interesting.
Initially I thought that the tricky range for $n$ would only be small (below $10^6$ or so) and for larger $n$ we could apply some simple greedy algorithm that prefers division by 3 or 4, even if we need to subtract 1 first. I tried to test some identities that could lead to such a heuristic:

*

*$f(n) = 1 + f(n - 1)  \ \ \forall n: n \equiv 1,5 \pmod{6}$ (that's easy to prove, because there's only one valid move)

*$f(n) = \min \{ f(\frac{n}{2}), f(\frac{n}{3}) \} \ \ \forall n: n \equiv 0 \pmod{6}$

*$f(3n) \geq f(n)$

*$f(n) = f(\frac{n}{3})  \ \ \forall n: n \equiv 0 \pmod{3^3}$

*$f(n) = f(\frac{n}{3})  \ \ \forall n: n \equiv 0 \pmod{3} \textbf{ and } n \not\equiv 0 \pmod{2}$

*...

But all but the first three have turned out not to be correct, and those are not very helpful because you still have a branching factor of 2. You can use the third inequality to prune during a depth- or breadth-first search, but I also can't prove that this yields a "good" algorithm, $O(\log^c n)$ or something.
I understand that it might have something to do with the exponents of 2 and 3 in the prime factorization of $n$, but I can't put my finger on it, since you always have the possibility to get to any equivalency class modulo 2 or 3 within at most 2 steps and change up everything.
Do you have any ideas on how to formalize this or prove useful properties of the $f$ function? I'm not only looking for approaches that necessarily lead to an algorithm for larger $n$, also for general insights that have escaped me so far.

We will use a very straightforward method that produces a solution of order o(N), still though not polynomial in the size of the input.
We will use the following recursive function to calculate the result:
$$m(N) = 1 + min( Ν \ mod \ 2 + m( \frac{N}{2} ), N \ mod \ 3 + m( \frac{N}{3} ) )$$
$$m(1) = 0$$
The correctness of the above method is obvious, we pretty much try every possible way to reduce the number to 1.
The total amount of operations for the above method is given by the following recurrence relation:
$$ T(N) = T(\frac{N}{2}) + T(\frac{N}{3}) + O(1) $$
To analyze this relation, we cannot use the master theorem since this relation is not in the appropriate form. We have to use the Akra-Bazzi method. In short, what the method says is that if we have a recurrence relation of the following form:
$$ T(x) = g(x) + \sum_{i=1}^{k} a_i T( b_i x + c_i ) $$
Then we can found the asymptotic behaviour of T(x) by first determining the constant $p \in \mathbb{R}$ such that $\sum_{i=1}^{k} a_i b_i^p = 1$ and then evaluating the following integral:
$$I(x) = \int_1^x \frac{g(u)}{u^{p+1}} du$$
Then we know that $ T(x) \in \Theta( x^p ( 1 + I(x) ) ) $.
We will now apply this method to our problem. We know that $g(x) \in O(1)$ and furthermore $a_1=a_2=1, b_1 = \frac{1}{2}, b_2 = \frac{1}{3}$. Evaluating the integral gives us:
$$ I(x) = \int_1^x \frac{g(u)}{u^{p+1}} du = \int_1^x u^{-(p+1)}du = \frac{-x^{-p}}{p} + \frac{1}{p} = \frac{1 - x^{-p}}{p} $$
Finally by substituting we get: $ T(x) \in \Theta( x^p( 1 + I(x) ) ) = \Theta( x^p ) $.
What remains to be done is to find the value of p. We solve the following equation, $2^{-p} + 3^{-p} = 1$, by analytically computing its root (we can use either the Newton-Raphson or the bisection method) we obtain that p = 0.78788...
Therefore, the complexity of our algorithm is of order $O( N^{0.79} )$.
For further details for the Akra-Bazzi method you can check here: https://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method
