# Two button calculator part 2

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). Can you use this calculator to reach every positive integer when starting with 1?

Here is a similar question: Two button calculator

• The question is if this is a kind of reversed Collatz conjecture or a significantly different thing. In the first case there is no proof yet. – balazs.com Nov 16 '19 at 17:04

Sorry that I ignored that comment of yours in the other post.

Proof: Note that the number $$\alpha = \log_32$$ is irrational. This implies that the sequence $$(\{ k\alpha\})_{k \geq 0}$$ is dense in the interval $$[0,1)$$, where $$\{\cdot\}$$ denotes the fractional part.

Now let $$n$$ be an integer and consider the interval $$[\log_3n, \log_3(n + 1))$$. Its image under the map $$\{ \cdot \}:\mathbb R \rightarrow [0, 1)$$ contains a non-empty open set. Hence there exists infinitely many integers $$k\geq0$$ such that $$\{ k\alpha \}$$ lies in the image of that interval.

We take such a $$k$$ that is sufficiently large, so that $$k\alpha \geq \log_3n$$. Then there is an integer $$m\geq0$$ such that $$k\alpha - m$$ lies in the interval $$[\log_3n,\log_3(n + 1))$$.

Therefore we get the number $$n$$ via $$\lfloor \frac{2^k}{3^m}\rfloor$$.

• Ah cool! I am guessing this doesn't give the minimal number of steps though? – Dmitry Kamenetsky Nov 16 '19 at 19:51
• @DmitryKamenetsky This is far from the minimal number of steps. For example, this algorithm needs $13$ steps to get $6$. And to get $30$ you need $98$ steps... – WhatsUp Nov 16 '19 at 21:46
• It is actually quite easy to apply this. Start with the value $1$. If the current value is less than the goal value $n$ then double it, and if it is $n+1$ or greater then divide by $3$ (without rounding down). Repeat until you get a value between $n$ and $n+1$. Let $k$ be the number of doublings you needed, and $m$ the number of divisions by $3$. This means that you can get to $n$ by doing $k$ doublings followed by $m$ divisions by $3$ with rounding down. – Jaap Scherphuis Nov 16 '19 at 22:04

I started making the numbers progressively by hand. The even numbers are easy to compute. (Twice of another lower number). Odd numbers which are divisible by 3 also make unbroken chains (3>6>12>24>48>96 and 9>18>36>72).

• $$1$$
• 1>$$2$$
• 1>2>4>8>16>5>10>$$3$$
• 1>2>$$4$$
• 1>2>4>8>16>$$5$$
• 3>$$6$$
• 4>8>16>32>64>21>$$7$$
• 4>$$8$$
• 7>14>28>$$9$$
• 5>$$10$$
• 10>20>40>13>26>52>17>34>$$11$$
• 6>$$12$$
• 10>20>40>$$13$$
• 7>$$14$$
• ??????
• 8>$$16$$
• 13>26>52>$$17$$
• 9>$$18$$
• 11>22>44>88>29>58>$$19$$
• 10>$$20$$

Here is how each number upto 20 can be written. Note that I could not find a representation for 15.

• 1>>16>5>>160>53>106>35>70>23>46>15 – Daniel Mathias Nov 16 '19 at 22:22
• @DanielMathias Nice. I wasn't going deep enough to get it. – SmarthBansal Nov 16 '19 at 22:45