Efficient algorithm for getting from 1 to n with 3 specific operations

Question

The question:

Given those 3 valid operations over numbers and an integer $n$:

• add $1$ to the number
• multiply the number by $2$
• multiply the number by $3$

describe an efficient algorithm for the minimal number of operations of getting from $1$ to $n$ with the 3 operations mentioned above.

For example for $n=28$ the answer is $4$ : $1\times 3\times 3\times 3+1=27+1=28$.

My approach:

I noticed that there is a recursive algorithm that will provide the answer but even when I used memoization the algorithm took a lot of time to end with $n\geq 1000$. I thought of a way to start with $n$ instead and try to reduce it to $1$ with the inverse operations of subtracting $1$ dividing by $2$ or by $3$ and trying to get it to be devisible by $3$ or by $2$ by subtracting $1$'s and checking the mod. But my second approach had some (more than some) mistakes where It stated that the smallest number of operations is more than it is. Please help or give a hint I clearly missing some kay fact about the nature of such operations.

Edit:

def ToN(n):

d=dict()
def to(x,num,di):
    if (num==x):
        return 0
    elif (num>x):
        return num
    elif num in di:
        return di[num]
    else:
        if num+1 not in di:
            di[num+1]=to(x,num+1,di)
        if num*2 not in di:
            di[num*2]=to(x,num*2,di)
        if num*3 not in di:
            di[num*3]=to(x,num*3,di)
        di[num]=min(di[num+1],di[num*2],di[num*3])+1
        return di[num]
return to(n,1,d)

I wrote the code above in python and it takes a lot of time to end for num=1000. Can you help me understand what is wrong w.r.t. efficiency.

Answer 1

Find the shortest path from $1$ to $n$ on an appropriate graph on vertices $\{1, \dots, n\}$. This approach will work whenever it's guaranteed that intermediate values in the calculations will lie within some bounded range.

Answer 2

An optimal solution will start with x = 1 and repeatedly replace x with 2x (1 step), 2x+1 (2 steps), 3x (1 step), 3x+1 (2 steps) or 3x+2 (3 steps).

I'd attack the problem from both ends: Find the shortest way from 1 to x, and how many steps it takes, for every x ≤ $n^{1/2}$ , and find the ways back from n to a number x ≤ $n^{1/2}$, then combine both. That should work in $O (n^{1/2})$.

For example n = 196 (just a random number)

1. 0 steps
2. 1 step
3. 1 step
4. 2 steps
5. 3 steps
6. 2 steps
7. 3 steps
8. 3 steps
9. 2 steps
10. 3 steps
11. 4 steps
12. 3 steps
13. 4 steps
14. 4 steps

From 196: 0 steps From 98: 1 step From 65: 2 steps From 49: 2 steps From 32: 4 steps From 24: 4 steps From 21: 5 steps From 16: 4 steps From 12: 5 steps From 10: 7 steps From 8: 5 steps From 7: 6 steps From 5: 6 steps

So there are two ways to get there in 8 steps. 1 -> 8 -> 98, and 1 -> 12 -> 98. The calculation was much quicker than O (n).

If you needed to solve this for multiple values n, I'd probably make the table of small values larger. For example, 100 values n around 1 million, I'd start with a table up to 10,000.

Edit about comments: In an optimal chain, x2 cannot be followed by +1, +1 because adding one before the multiplication would be shorter. And x3 cannot be followed by +1, +1, +1 because adding one before the multiplication would again be shorter. At the start with x = 1, we may assume that we don't add +1 once or twice because we can multiply by 2 or 3 instead. So there is always an optimal chain that consists of x2 possibly followed by +1, or x3 possibly followed by +1 or +2.

Finding all optimal solutions up to some k can clearly be done in a total of k steps. k = n^(1/2) means n^(1/2) steps. I assumed going backwards from to some x ≤ n^(1/2) would divide n by some k not much larger than n^(1/2) so could also be done in n^(1/2).

BUT you can actually do much better. By working your way backward, if the number of steps needed is S (n), then S (n) = min (S (floor (n/2)) + 1 + (n modulo 2), S (floor (n/3)) + 1 + (n modulo 3)). You either subtract 1 as long as the number is not divisible by 2, then divide by 2, or you subtract 1 as longas the number is not divisible by 3, then divide by 3.

One step back divides quite exactly by 2 or 3. There are only about log (n) steps going backwards. There are only about (log (n))^2 combinations of divisions by 2 or 3, because you end up at the same number no matter in which order you make steps dividing be 2 or 3. So you can easily find an optimal chain in O ((log (n))^2).

For example, if n = 1234567, then you can easily find the optimal chain 1 -> 2 -> 4 -> 5 -> 15 -> 45 -> 46 -> 47 -> 141 -> 423 -> 1269 -> 1270 -> 3810 -> 11430 -> 11431 -> 22862 -> 68586 -> 68587 -> 137174 -> 411522 -> 1234566 -> 1234567 (21 steps).