# Traveling between integers- powers of 2

Moderator Note: At the time that this question was posted, it was from an ongoing contest. The relevant deadline has now passed.

Consider the integers. We can only travel directly between two integers with a difference whose absolute value is a power of 2 and every time we do this it is called a step. The distance $d$ between two integers is the minimum number of steps required to get from one to the other. Note however that we can travel backwards. For instance $d(2,17)$ is 2: $2+16=18 \rightarrow 18-1=17$.

How can we prove that for any integer n, we will always have some $d(a,b)=n$ where$b>a$?

If we are only able to take forward steps I know that the number of 1s in the binary representation of $b-a$ would be $d(a,b)$. However, we are able to take steps leftward on the number line...

-
Do we have the triangle inequality for this function $d(\cdot, \cdot)$? Note that this function is translation invariant : $d(a+c,b+c) = d(a,b)$. – Patrick Da Silva Mar 17 '12 at 3:30
I think that at some point you could add the tag number theory. (I did.) – Patrick Da Silva Mar 17 '12 at 3:44
@PatrickDaSilva: I believe we have the triangle inequality, because you if you want d(a,b) you can always do d(a,c)+d(c,b) and maybe there is a shorter way.. – Ross Millikan Mar 17 '12 at 4:03

It is easy to see that the function $s(n):=d(0,n)$ $\ (n\geq1)$ satisfies the following recursion: $$s(1)=1,\qquad s(2n)\ =\ s(n), \qquad s(2n+1)=\min\{s(n),s(n+1)\}+1 \ .$$ In particular $s(2)=s(4)=1$, $s(3)=2$. Consider now the numbers $$a_r:={1\over6}(4^r+2)\qquad (r\geq2)$$ satisfying the recursion $$a_2=3,\qquad a_{r+1}=4 a_r-1\quad (r\geq2).$$ The first few of these are $3$, $11$, $43$, $171$. I claim that $$s(a_r-1)=s(a_r+1)=r-1,\quad s(a_r)=r\qquad (r\geq2)\ .$$ The claim is true for $r=2$. Assume that it is true for $r$. Then $$s(2a_r-1)=\min\{s(a_r),s(a_r-1)\}+1=r,\qquad s(2a_r)=r$$ and therefore $$s(4a_r-2)=s(4a_r)=r,\quad s(4a_r-1)=\min\{s(2a_r),s(2a_r-1)\}+1=r+1\ .$$ The last line can be read as $$s(a_{r+1}-1)=s(a_{r+1}+1)=r, \qquad s(a_{r+1})=r+1\ .$$

-

Presumably you mean every natural number $n$, not every integer $n$. We can simplify things by taking $a=0$ without loss of generality and then writing $d(b):=d(0,b)$. Also, it's enough to show that for every $n$ there is $b$ with $d(b)\ge n$, since that means that for all $n$ there are numbers not reachable in $n$ steps, and it then follows by induction that for all $n$ there are numbers reachable in exactly $n$ steps, since at each stage of the induction there are adjacent numbers of which one is reachable in $n$ steps and the other isn't, and the latter can be reached in an $(n+1)$-th step of $1$.

Now represent the integers in "infinite two's complement", that is, a non-negative integer is represented by its binary representation and a negative integer $k$ is represented by inverting the binary representation of $-(k+1)$, considered as a leftward infinite string with leading zeros. This puts the integers into bijection with the set of all leftward infinite binary strings with finitely many transitions between $0$ and $1$.

In this representation, adding a positive integer to a number works as expected, with carrying carried out until the infinite stretch of $0$s or $1$s is reached, and the $1$s flipped to $0$s by a carry.

Now in each step, we can add a positive power of two to the number we've reached, and then we can optionally flip its sign. (This is equivalent to adding or subtracting powers of two at each step.) Since flipping the sign means inverting the string and then adding $1$, in each step we can invert the string and add a power of two up to twice.

Inverting the string doesn't change the number of transitions between $0$ and $1$. Adding a power of two increases the number of transitions between $0$ and $1$ by at most $2$. Thus in each step we can increase the number of transitions by at most $4$. Since there are integers whose representations have arbitrary numbers of transitions, for every $n$ there are integers we can't reach in $n$ steps.

-
The end of the first paragraph "Also, it's enough to show that for every n there is b with d(b)≥n, since that means that for all n there are numbers not reachable in n steps, and it then follows by induction that for all n there are numbers reachable in exactly n steps, since at each stage of the induction there are adjacent numbers of which one is reachable in n steps and the other isn't, and the latter can be reached in an (n+1)-th step of 1." I hadnn't seen. Thanks. Then the idea of focusing on transitions instead of 1 bits is a good one.. – Ross Millikan Mar 17 '12 at 4:56
I actually meant integer: d(-3,-1)= 1, and d(-3,4)=2 as -3+8-1=4. I am afraid I do not understand your final sentence... how does that prove what we wanted to? – Ali Mar 17 '12 at 5:00
@Viktoria: You gave examples of $a$ being negative, not of $n$ being negative. I was only presuming that when you wrote "for any integer $n$", you meant "for every natural number $n$", since there are no negative numbers of steps. Regarding the final sentence, I had prepared for that with the induction in the first paragraph. The last sentence shows precisely what the first paragraph said was sufficient to show. – joriki Mar 17 '12 at 5:06

Consider $a(n) = \sum_0^n 2^{2i}$. Then $d(0,a(n)) = n + 1$.

Proof: First, note that in any minimal series of steps, you can only use each power of 2 once at most. If you add it twice at any point, you could get the same result by adding the next higher power once (and if that one was used, iteratively until the first unused one), same for substraction, and obviously adding it once and substracting it once would cancel out entirely, each leading to the same result with less steps.

Also, we can do the steps in arbitrary order, so we can assume we do all additions first.

Consider the binary representation of $a(n) = 10101...1$ with $n+1$ $1$s. A "step" is equivalent to addition or substraction of a power of $2$, and we start at $0$.

We start with the additions, so we can set any number of bits to $1$, each one being a step. Then we do the substractions, and those in order of magnitude, smallest first.

Any substraction of a power of $2$ will flip all $0$ to $1$ starting at its position and then moving up in significance until the first $1$ is encountered which then is flipped to $0$ (note that this is guaranteed to happen because our target number is positive and so the sum of added powers must be greater than the sum of substracted powers).

Now consider the bits in $a(n)$ starting at lowest significiance. Each $01$ pair in the final sum can only have resulted from one of three situations:

1. Having the power corresponding to the $1$ in the addition steps.

2. By resulting from $10$ and substraction of the power of $2$ corresponding to the $01$ bit pair or a lower power of $2$. But in that case, that $10$ must result from addition or substraction of that power of $2$.

3. Or, lastly, as a result of a substraction of a lower power of $2$ from $00$. But in that case, the result of the substraction would have been $11$ and thus, the power of two corresponding to the $0$ in that pair must also be substracted.

In 2. and 3. we made use of the fact that we can only use each power of $2$ once at most, so once a $1$ occurs at a point, substractions from below cannot go beyond it (as $\sum_{i \lt n} 2^i \lt 2^n$).

Thus, we require at least one step for each $01$ pair and the claim is proven.

Additionally, any number $b$ with $d(0,b) = n+1$ must at least have $2n$ digits: Assume $b$ had less than $2n$ digits in binary representation. If $b$ contains $n$ or less 1s, we are done. And if there are at least $n+1$ $1$s and thus at most $n-2$ $0$s, then we have a procedure to generate $b$ in $n$ steps: Start with $2^{2n}-1$ in two steps resulting in $1...1$, and then in an additional $n-2$ substractions we substract all powers of $2$ that correspond to a $0$ in the binary representation of $b$. As $d(0,1011_b)=3$ shows, there are numbers with just $2n$ digits, though, so $a(n)$ is not optimal.

-

Hint: If you represent the integers in binary, one way to build up a number from zero is to add the powers of $2$ that are one bits in the representation. As you have shown, there may be a faster way. See if you can find a set of numbers where the $1$'s are far enough apart that this is the fastest way to get there.

-
He wants to show that you can hit every positive integer $n$ with the distance : it is possible that with adding minus sign possibilities, that this distance may not be surjective. You didn't answer the question. This may be hard to do : for instance, $$d(a,a+2^n + 2^{n-1} + \dots + 1) = d(a, a+2^{n+1}-1) = 2$$ – Patrick Da Silva Mar 17 '12 at 3:32
@PatrickDaSilva: I missed that you had to start with a given $a$, but I don't think that changes the argument. You just multiply the numbers in the set starting with $0$ by 2^(one more than the largest power of $2$ in $a$). – Ross Millikan Mar 17 '12 at 3:35
You don't have to, I just assumed that if you write $d(a,b)$, you might as well express $b$ as $a + something$, and I worked out something where your trick might not be relevant. At least it doesn't help me find something – Patrick Da Silva Mar 17 '12 at 3:38
@PatrickDaSilva: I believe we only have to prove there are numbers at every distance from $0$ and was prompted by the Liouville numbers. I think you can prove that $d(0,\sum_{i=1}^n 2^{n!})=n$ – Ross Millikan Mar 17 '12 at 4:00
Isn't the something just the difference between b and a? Anyhow I think that only b-a matters as d(a,b)=d(c,d) when d-c= b-a. – Ali Mar 17 '12 at 4:15

I think joriki's argument can be simplified a bit :

with $n$ steps, supposing you don't do stupid things like using the same power of $2$ twice or more, the number of integers you can reach using $n$ powers up to $2^k$ is at most $2^n \binom{k}{n} = P_n(k)$ where $P_n$ is a polynomial (of degree $n$). Meanwhile, if you can reach a number $x < 2^l$ in $n$ steps, then you can't use arbitrarily high powers of two : if you use $2^k \ge 2^{l+n}$ then you can't substract enough smaller powers from it to get down to $x$.

The number of integers in $]-2^l, 2^l[$ is $2^{l+1}-1$, which is exponential in $l$, but the number of those you can reach in $n$ steps is less than $P_n(l+n) = Q_n(l)$, which is polynomial of degree $n$ in $l$. Therefore for $l$ big enough you will necessarily miss some of those numbers, so the number of steps needed to reach all the integers is unbounded.

-