A simple two-operation calculator. How to obtain any natural number from any other?

Imagine that you possess a very simple electronic calculator. It has a screen and ten buttons from 0 to 9 to enter natural decimal numbers (positive integers). However, it can perform just two unary operations, and that's all. Either:

1. it can multiply the input number by 2 (e.g. 50 becomes 100); or
2. it can delete the last digit of the input number (e.g. 50 becomes 5).

Assuming that you have entered a certain number, be it A. How must you act in order to obtain another specified number, be it B? The problem asks for finding a universal algorithm, so you can obtain any number from any other.

• Are you aware of such a universal algorithm? Also, does the length of the algorithm matter? Dec 17 '20 at 21:00
• There is no universal algorithm. If the starting number is 0, you can't get anywhere other than 0. Dec 17 '20 at 21:14
• Here is a related previous question: Two button calculator. Dec 17 '20 at 22:01
• @user253751 The natural number condition means the starting number can't be 0, I think. Dec 17 '20 at 22:30

Given that both A and B are positive integers, the first step is

convert A to the number 1

which is easy:

Multiply by 2 until the highest digit overflows to create a new 1 digit, and erase all the lower digits to just leave a single 1.

The next part

of converting the number 1 to an arbitrary given number B

is hard but can be always done in finitely many steps:

We will be searching for a power of 2 that starts with B. If we find it, we can start from 1, multiply by 2 until we reach that particular power of 2, and erase the last digit until we get B.

The inequality to solve is

$$B\times 10^m \le 2^n < (B+1)\times 10^m \\ m+\log_{10}{B} \le n \log_{10}{2} < m+\log_{10}(B+1) \\ \text{frac}(\log_{10}{B}) \le \text{frac}(n\log_{10}{2}) < \text{frac}(\log_{10}{(B+1)})$$

Because $$\log_{10}{2}$$ is irrational,

the inequality always has an integer solution for $$n$$. For a number-theoretic argument, choose a sufficiently large prime $$p$$ so that $$k/p$$ approximates $$\log_{10}{2}$$ sufficiently well for some integer $$k$$. If $$m/p$$ is inside the given interval, $$n=mk^{-1} \text{ mod } p$$ is a solution. (I forgot the relevant theorem's details and I'm not sure if this number-theoretic argument is valid, but I'm pretty sure the result still holds.)