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

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.

• Hint: Use dynamic programming to get an $O(n)$ algorithm. I'll let you fill in the details. – Yuval Filmus Jun 9 '16 at 8:08
• What specifically did you try? "took a lot of time" is not a lot to go on. – Raphael Jun 9 '16 at 9:52
• Your first approach should have worked, and should have been really fast. You must have programmed it inefficiently somehow. – Peter Shor Jun 9 '16 at 12:22
• This isn't the right stackexchange for debugging code. But where's the memoization? – Peter Shor Jun 9 '16 at 16:32
• Your code is wrong. Think again. – Yuval Filmus Jun 9 '16 at 20:27

2 Answers

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.

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).

• So you will have two optimal chains, but is it globally optimal? – Evil Jun 10 '16 at 13:40
• Why will every solution have the form you claim? What's special about $\sqrt{n}$ that allows you to find out the answer by looking at the shortest route from $1$ to $x\in\{1, \dots, \lceil \sqrt{n}\rceil\}$ and then from $x$ to $n$? Why can't you get an $O(\sqrt[3]{n})$ algorithm by just considering intermediates up to $\lceil\sqrt[3]{n}\rceil$? – David Richerby Jun 10 '16 at 14:20
• Actually, the real killer: Why do you feel that you can find the number of steps from $1$ to $\sqrt{n}$ in constant time but finding the number of steps from $1$ to $n$ takes more-than-constant time? – David Richerby Jun 10 '16 at 14:22
• The longest chain (hailstone?) is at most $2\lceil log_2(N)\rceil$ and the shortest is exactly $log_3(N)$. If you take $3^{20}$ it has $20$ numbers in the chain. $sqrt(3^{20}) = 531441$, so what it represents? – Evil Jun 10 '16 at 16:25
• The fact you can reach $1234567$ in 21 steps does not prove your algorithm is $O((\log n)^2)$. To find that you'd have to make much more recursive backward steps, according to your equation for $S(n) = \min (S (\lfloor n/2 \rfloor) +...)$, since you fork each $n$ into (approx.) $n/3$ and $n/2$ and solve the problem for 2 (smaller) cases now, which looks like $O(n)$. – Anton Trunov Jun 11 '16 at 8:53