Construction of positive integers by given rules

Question

For a positive integer n there are two operations defined:

1. append one of the digits 0, 4 or 8 at the right end of n
2. n can be divided by 2 if n is even

Start number is 4. Is it possible to construct any positive integer with those two rules?

Example to construct 55: 4→44→22→220→110→55

Answer 1

The answer is

yes.

Easy proof:

Do it back to front: Start with the desired number, multiply by 2 until the last digit is 0,4 or 8 and strike out the last digit and start over if necessary. As we can easily check this is always possible with at most 3 doublings each cycle decreases the number so we must eventually arrive at a single digit. Again, it is easily verified that from there we can get to 4.

Answer 2

It

is

possible to construct every positive integer this way. Proof:

Suppose not, and let $n$ be the smallest positive integer you can't construct. First of all, $n$ is more than one digit long because all single-digit positive integers are constructible. (4 -> 2 -> 1 -> 10 -> 5; 2 -> 24 -> 12 -> 6 -> 3; 1 -> 14 -> 7; 1 -> 18 -> 9; 6 -> 64 -> 32 -> 16 -> 8.) So $n=10m+d$ where $d$ is its last digit and $m$ is also a positive integer. In particular $m$ is constructible since $m<n$ and hence so are $10m+0,4,8$ so we know that $d$ isn't any of those. Likewise, $2m$ is constructible since $2m<n$ and hence so is $(10\cdot2m+4)/2=10m+2$; $4m$ is constructible since $4m<n$ and hence so is $(10\cdot4m+4)/4=10m+1$. So $d$ isn't any of $0,1,2,4,8$. $4m+2$ is constructible since $4m+2<n$ and hence so is $(10\cdot(4m+2)+4)/4=10m+6$; $8m+2$ is constructible since $8m+2<n$ and hence so is $(10\cdot(8m+2)+4)/4=10m+3$. So $d$ isn't any of $0,1,2,3,4,6,8$. $2m+1$ is constructible, hence so are $(20m+10,14,18)/2=10m+5,7,9$ so $d$ isn't any of $5,7,9$. And that's all the possible last digits, so we're done.