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.

  • 2
    $\begingroup$ Are you aware of such a universal algorithm? Also, does the length of the algorithm matter? $\endgroup$
    – bobble
    Dec 17 '20 at 21:00
  • 6
    $\begingroup$ There is no universal algorithm. If the starting number is 0, you can't get anywhere other than 0. $\endgroup$
    – user253751
    Dec 17 '20 at 21:14
  • $\begingroup$ Here is a related previous question: Two button calculator. $\endgroup$ Dec 17 '20 at 22:01
  • $\begingroup$ @user253751 The natural number condition means the starting number can't be 0, I think. $\endgroup$
    – ripkoops
    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.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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