Csdrhrt

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(lfloorfrac{n}{2}rfloor), (nmod 3) + f(lfloorfrac{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 notequiv 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.

Just a bit of statistics: Up to a billion, worst case is 644,972,543 with 44 moves. Up to 4 billion, worst case is 3,386,105,855 with 48 moves. 99% of all numbers to 36 moves or fewer, 99.99% take 39 moves or fewer.

The simple algorithm "Divide by 3 if possible, else divide by 2 if possible, else subtract 1" has the worst case numbers 3 * 2^k - 2 taking 2k steps and 3 * 2^k - 1 taking 2k + 1 steps, which is substantially worse.

It's a elementary dp problem.

for recursive solution:
First, you can run dp function upto 10^7 using memozition in O(n).
And then write another similar function for bigger numbers, this time run the function without memozition. if the number you call becomes less than 10^7, return the value from previously function.

observations:
what can be maximum output of all the numbers?

• 2^30 > 10^9


• 3^17 > 10^9


• And you know you can reduce a number n by 1 if n/2 & n/3 doesn't give optimal solution.

suppose, a number p is a prime.

then, at first step, we reduce it to (p-1) & then call it again. This (p-1) is obviously divisible by 2 or 3. For worst case, I assume it is divisible by 2. then, we call (p-1)/2.
let, p = (p-1)/2.

so we need 2 moves to reduce a number at it's half. if this new p is prime again, we repeat the steps. So what can be maximum output? I guess 60. But practically, It'll be at most 40.

Another guess, what's the maximum move of a greater than 10^7 to reduce it upto 10^7?

Practically, first function O(n), 2nd function O(3^m), where m <= 12.
the 2nd function I referred that can be like this one: http://paste.ubuntu.com/7131241/

Sorry, for bad English.

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