9
$\begingroup$

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

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – balazs.com
    Nov 16, 2019 at 17:04

2 Answers 2

Reset to default
8
$\begingroup$

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

In fact the answer is "yes": every number can be made.

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ Ah cool! I am guessing this doesn't give the minimal number of steps though? $\endgroup$
    – Dmitry Kamenetsky
    Nov 16, 2019 at 19:51
  • 1
    $\begingroup$ @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... $\endgroup$
    – WhatsUp
    Nov 16, 2019 at 21:46
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jaap Scherphuis
    Nov 16, 2019 at 22:04
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 1>>16>5>>160>53>106>35>70>23>46>15 $\endgroup$
    – Daniel Mathias
    Nov 16, 2019 at 22:22
  • $\begingroup$ @DanielMathias Nice. I wasn't going deep enough to get it. $\endgroup$
    – SmarthBansal
    Nov 16, 2019 at 22:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.