# Construction of positive integers by given rules

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

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.

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 and hence so are $$10m+0,4,8$$ so we know that $$d$$ isn't any of those. Likewise, $$2m$$ is constructible since $$2m and hence so is $$(10\cdot2m+4)/2=10m+2$$; $$4m$$ is constructible since $$4m 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 and hence so is $$(10\cdot(4m+2)+4)/4=10m+6$$; $$8m+2$$ is constructible since $$8m+2 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.

• Did you just beat me to it by 11 secs? – loopy walt Apr 1 at 23:53
• It sure looks like it :-). Your proof is cleaner than mine, though. (Well, of course they're basically the same proof. But I went the route of showing all the cases separately, which I think was suboptimal given that one can summarize the process more neatly and uniformly as you did.) – Gareth McCaughan Apr 2 at 0:17
• Thanks! As pretexts (for not deleting my answer) go this is good enough for me ;-) – loopy walt Apr 2 at 0:23