2

Binary Patterns: An Answer

My last post put forward the challenge to find numbers whose binary representations end with their decimal representations, like how $11 = 1011_2.$

It turns out that there are lots of them. Infinity of them, in fact.

If we’re going to try to find those numbers, the first thing to realize is that the binary representations only use 0s and 1s, so the only decimal numbers that have any chance of working out will be strings of those two digits. If we begin looking at those numbers, it starts to look like all of them will fit the bill.

However, if we persist a little further, we find one that doesn’t:

$$ 1010 = 1111110010_2 $$

Why doesn’t 1010 work? Let’s actually come back to that question in a moment. It will be easier to understand why $1010$ doesn’t work if we first see some things that do.

First, I claim that all powers of 10 (1, 10, 100, 1000, and so on) do work. In our ordinary decimal system, the number $10^k$ is written as $1\underbrace{00\cdots 0}_{k\text{ zeroes}}$. Similarly, because the binary system treats $2$ like the decimal system treats $10$, we can say that $2^k = 1\underbrace{00\cdots 0_2}_{k\text{ zeroes}}$. Now, bear with me: I’m going to look at the binary representation of $10^k-2^k$. It turns out that $$ 10^k-2^k = \underbrace{??????\cdots ??????}_{\text{unimportant digits}}\underbrace{000\ldots 0}_{k+1\text{ zeroes}} .$$ We can see this by factoring:

$$ 10^k – 2^k = (5\cdot 2)^k-2^k = 5^k\cdot 2^k-2^k = (5^k-1)\cdot 2^k .$$

We know that $5^k$ is an odd number, and so $5^k-1$ is an even number. We can use $2m$, where $m$ is an integer, to represent $5^k-1$. Then, continuing where we left off,

$$ 10^k – 2^k = 2m\cdot 2^k = m\cdot 2^{k+1} .$$

And this is what we needed: $10^k-2^k$ is divisible by $2^{k+1}$, so its binary representation will end in $k+1$ 0s. Now we imagine what happens when we add $2^k$ back to it:

Since the last $k+1$ digits of the binary representation of $10^k-2^k$ are all 0s, when we add to it the binary representation of $2^k$, which is just a 1 followed by $k$ 0s, we just see the 1 with $k$ 0s again. Therefore, the binary representation of $10^k$ ends with the decimal representation of $10^k$.

Now that we know that all powers of $10$ fit this pattern, we can find others that do as well. For example, any number that is one more than a power of $10$ also works, since all that changes is that we swap a 0 for a 1 at the end of the binary and decimal representations:

But we can also see why some numbers don’t work. Let’s return to $1010$. We already know that the binary representation of 1000 ends with 1000, and in our table above, we see that the binary representation of 10 is 1010. So when we add these numbers, we are forced to carry in the 4th position from the right:

It looks like it may actually be a little bit messy to describe exactly which numbers do and do not fit the pattern, but at least we’ve got a pretty good start here, and that will have to do for now.

 

2 Comments

  1. Why not just say $10^k/2^k=5^k$ is an odd number? Then adding $k$ zeroes after the base 2 representation of $5^k$ gives you the base 2 representation of $10^k.$

    • That’s definitely a valid way to show that all powers of 10 fit the pattern. I presented it this way because the addition aspect helps us think about the other numbers (1 more than powers of 10, the number 1010) that may or may not work.

Comments are closed.