Two button calculator

A calculator has only 2 buttons. The first multiplies the current value by 2, the second divides it by 3 without a remainder (so 8 becomes 2). Starting with 1 what is the least number of presses you need to reach 9?

Here is a similar question: Three button calculator

I found the fewest number of button presses as

11 presses.

We get

9 by multiplying 1 by 2 eight times, giving 256, and then dividing by 3 three times. 256 -> 85 -> 28 -> 9.

I don't see a possibility to do it in fewer, but I'll try to prove it.

EDIT:

Following the comment below, I continued searching and found another five solutions for n = 11.

These are:

1 -> 2 -> 4 -> 8 -> 16 -> 32 -> 64 -> 128 -> 42 -> 84 -> 28 -> 9
1 -> 2 -> 4 -> 8 -> 16 -> 32 -> 64 -> 128 -> 42 -> 14 -> 28 -> 9
1 -> 2 -> 4 -> 8 -> 16 -> 32 -> 64 -> 21 -> 42 -> 84 -> 28 -> 9
1 -> 2 -> 4 -> 8 -> 16 -> 32 -> 64 -> 21 -> 42 -> 14 -> 28 -> 9
1 -> 2 -> 4 -> 8 -> 16 -> 32 -> 64 -> 21 -> 7 -> 14 -> 28 -> 9

• My intended answer also uses 11 presses, but arrives there very differently. Fascinating. Nov 12, 2019 at 16:54
• Using a computer, I can verify that it is indeed the minimun number of presses needed. Nov 12, 2019 at 16:59
• There's only a thousand ($2^{10}$) possibilities to rule out, so checking with brute force should be pretty trivial.
– Bass
Nov 12, 2019 at 16:59
• But note that changing the number $9$ to something like $121$ or $127$ would indeed make the puzzle more challenging. Nov 12, 2019 at 17:02
• I updated my answer to include the remaining 5 solutions requiring 11 presses.
– user63738
Nov 12, 2019 at 17:05

Computerless proof that CDJB's solution is best possible (which also finds all possible solutions in that many steps, though I haven't filled in the details of that part since you can see the explicit solutions in CDJB's answer):

We can get to 9 only from 27, 28, or 29. (One step.) We can get to those from anything in [81,89] -- this notation denotes a closed interval, including its endpoints -- or by doubling 14. (Two steps.) We can get to those from anything in [243,269], or anything in [41,44], or by doubling 7. (Three steps.) We can already see a solution by doubling 8 times to reach 256. We don't have enough doublings available to get into [243,269] in fewer than 8 more steps, so if there's a solution that uses fewer than 11 in total it must go via [41,44] or 7. We can get to those from anything in [123,134] or [21,23] or by doubling 21 or 22 -- note that those last two don't add anything to the [21,23] we already had. (Four steps.) Again we can see that we could go via 128 in 11 steps; if we use fewer steps we can't reach [123,134] with the number of doublings available, so we'd have to go via [21,23]. We can get to those from anything in [63,71] or by doubling 11. (Five steps.) Again we could use 64, and now everything that's left is out of range if we use <=5 more steps, since that can't take us above 32. Done.

Credit where due: isaacg pointed out, in comments, a couple of bugs in my analysis, and while fixing those I found another one. Thanks, isaacg!

• You left out a couple posibilities, making this proof not quite rigorous. For instance, the sequence 41 -> 82 -> 27 -> 9 is a possibility you omit. Likewise, 11 -> 22 -> 7 -> 14 -> 28 -> 9. If you fix these couple of bugs, the proof should be fine. Nov 13, 2019 at 17:27
• Yup, those are bugs. (One was an arithmetic error, one was actually overlooking a possibility.) I found another little bug too. I think I've fixed them all now. Nov 14, 2019 at 0:08

This is very straightforward. The only rule is not continuing to lower level in case there would be a number repeat.