# Investigation: Faster Conversion through Bases

Let's start with a simple problem: Convert $$10100111_2$$ to base $$4$$.

We first convert $$10100111_2$$ to base $$10$$, then convert that to base $$4$$, as shown by the Number Base Representation article.

We see that $$10100111_2=1+2+4+32+128=167$$. Now we convert this into base $$4$$:

How many times does $$4^4=256$$ go into $$167$$? None, we go down to test the next place.

How many times does $$4^3=64$$ go into $$167$$? $$2$$ times. Now we multiply $$2$$ by $$64$$ to get $$128$$, and subtract this from $$167$$ to get $$39$$.

How many times does $$4^2=16$$ go into $$39$$? Twice, so we multiply $$16$$ by $$2$$ to get $$32$$, and subtract that from $$39$$ to get $$7$$.

How many times does $$4^1=4$$ go into $$7$$? $$1$$ time, so we subtract $$4$$ from $$7$$ to get $$3$$.

How many times does $$4^0=1$$ go into $$3$$? $$3$$ times. Finally, our answer is $$2213_4$$.

Phew, that was a pretty calculation-heavy problem. If only there was an easier way...

Let's look at our original base $$2$$ number and our base $$4$$ number more closely: $$10100111\iff 2213$$. Do you notice anything interesting?

How about if I do this: $$10|10|01|11\iff 2|2|1|3$$?

We notice that in each little subdivision, the base $$2$$ representation is automatically converted to the base $$4$$ representation, independent of anything else! For example, $$10_2=2_4$$, $$01_2=1_4$$, and $$11_2=3_4$$.

Why does this work? Let's observe what is happening, fundamentally: We can represent

$$10100111_2=1\times 2^7+0\times 2^6+1\times 2^5+0\times 2^4+$$$$0\times 2^3+1\times 2^2+1\times 2^1+1\times 2^0$$.

Let's see what happens when we group this as follows: $$10100111_2=(1\times 2^7+0\times 2^6)+(1\times 2^5+0\times 2^4)+$$ $$(0\times 2^3+1\times 2^2)+(1\times 2^1+1\times 2^0)$$

Now we factor out the common multiple in each box:

$$10100111_2=2^6(1\times 2^1+0\times 2^0)+2^4(1\times 2^1+0\times 2^0)+$$ $$2^2(0\times 2^1+1\times 2^0)+2^0(1\times 2^1+1\times 2^0)$$

Simplifying, we get that $$10100111_2=2\times 4^3+2\times 4^2+1\times 4^1+3\times 4^0$$

But wait a minute! The stuff on the $$\text{RHS}$$ is exactly what a base $$4$$ representation looks like! Therefore, we can clearly see that $$10100111_2=2213_4$$.

Here is the trick in practice: We see that to convert base $$2$$ to base $$4$$, we group into groups of 2. So we have $$10100111\implies 10|10|01|11$$.

We see that $$10_2=2_4$$, $$10_2=2_4$$, $$01_2=1_4$$, and $$11_2=3_4$$. Therefore our answer is $$\boxed{2213_4}$$. You can see how much faster this is than to convert to base $$10$$, then back to base $$4$$.

It turns out that to convert a base $$2$$ number to a base $$2^x$$ number, we group the original number's digits into groups of $$x$$. I'll prove this later.

How about this problem: Convert $$10100111_2$$ to base $$8$$.

Thinking along the lines of our previous exercise, we try to group the digits in $$10100111_2$$ to get the base representation of a number base $$8$$.

Seeing that $$2^3=8$$, let's try groupings of threes.

We try to group $$10100111_2$$ into groups of threes, but we can't, because there are $$8$$ digits and $$8$$ isn't divisible by $$3$$. What do we do?

Well, we want there to be $$9$$ digits, so we simply add a $$0$$ at the beginning and there will be $$9$$ digits. It won't change the value of the number, so we are safe in doing this.

Now we can group as follows: $$10100111_2\implies 010|100|111$$.

Writing this out as the definition of a base number, we see that $$10100111_2=(0\times 2^8+1\times 2^7+0\times 2^6)+$$$$(1\times 2^5+0\times 2^4+0\times 2^3)+(1\times 2^2+1\times 2^1+1\times 2^0)$$

Factoring out and simplifying, we get that $$10100111_2=2\times 2^6+4\times 2^3 + 7\times 2^0$$.

Simplifying, we get that $$10100111_2=2\times 8^2 + 4\times 8^1+ 7\times 8^0=247_8$$ and we are done.

In practice, you won't go through all of these steps. You'll just see:

$$10_2=2_8$$, so the leftmost digit is $$2$$.

$$100_2=4_8$$, so the middle digit is $$4$$.

$$111_2=7_8$$, so the last digit is $$7$$ and our final answer is $$247_8$$.

This isn't limited to just powers of two; try this problem for yourself: Convert $$12002210_3$$ to base $$9$$.

Now we'll prove this cool trick for any arbitrary starting base $$b$$ converted into base $$b^x$$ for some positive integer $$x$$.

Let the starting number be $$(d_1d_2\cdots d_{nx})_b$$.

We are assuming that there is a multiple of $$x$$ digits in the number; if this is not the case, add leading $$0$$'s to the beginning of the number until this is the case.

We represent this number as $$d_1b^{nx-1}+d_2b^{nx-2}+\cdots +d_{nx}b^0$$.

Now we group the digits into groups of $$x$$ each: $$(d_1b^{nx-1}+\cdots + d_xb^{(n-1)x})+$$$$(d_{x+1}b^{(n-1)x-1}+\cdots +d_{2x}b^{(n-2)x})+\cdots +$$$$(d_{(n-1)x+1}b^{x-1}+\cdots +d_{nx}b^0)$$.

Factoring each group, we get $$b^{(n-1)x}(d_1b^{x-1}+\cdots +d_xb^0)+$$$$b^{(n-2)x}(d_{x+1}b^{x-1}+\cdots +d_{2x}b^0)+\cdots +$$$$b^0(d_{(n-1)x+1}b^{x-1}+\cdots +d_{nx}b^0)$$.

Changing $$b^{(n-i)x}$$ to $$(b^x)^{n-i}$$ for all $$i=1\rightarrow n$$, we get that $$(d_1d_2\cdots d_{nx})_b=(b^x)^{n-1}(d_1b^{x-1}+\cdots +d_xb^0)+$$$$(b^x)^{n-2}(d_{x+1}b^{x-1}+\cdots +d_{2x}b^0)+\cdots +$$$$(b^x)^0(d_{(n-1)x+1}b^{x-1}+\cdots +d_{nx}b^0)$$. This is exactly the base representation of a base $$b^x$$ number, so we are done.

You may think, after reading all of this, that this way of converting bases is way easier; you won't ever need to use the classic convert-to-10-then-to-desired-base trick. However, this is unfortunately not the case. This trick only works for converting a base $$b$$ number to a base $$b^x$$ number, i.e this trick will not work for converting a base $$6$$ number into a base $$3$$ number. This is because there is not way to group the digits so that one base turns into the other.

However, when in the occasion of changing a base $$b$$ number to a base $$b^x$$ number, you will know a neat and fast trick to do so. (These occasions happen frequently in competition math.)

Problems

*1. * Convert $$12321_4$$ to base $$16$$.

*2. * Convert $$112010032_4$$ to base $$8$$. Hint: do an intermediate conversion first.

*3. * Convert $$12345678_9$$ to base $$3$$.

*4. * Prove the formula for converting a base $$b^x$$ number to a base $$b^y$$ number.

Note by Daniel Liu
4 years, 3 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

Thanks for reading through my third #CosinesGroup post. I know this one is an especially long one, but it takes some explaining.

Sorry for any bad explaining on my part; I felt that my explaining for this was under par.

Feedback is appreciated. If you have any questions, feel free to ask.

I hope you learned something from this post,

~Daniel

- 4 years, 3 months ago

Thank you Daniel! It was great :)

- 4 years, 3 months ago

This is a useful trick in special scenarios. Another extention, is to convert from base $$b^x$$ to base $$b^y$$ by going through base $$b$$ as opposed to base 10. This is much faster, and avoids a bunch of arithmetic. Try the following:

Convert $$(1234567)_8$$ to base 4.

As a suggestion for improvement, it is generally best to clearly illustrate why this method is great. In the first example, I might have given the entire working, to show how this method is a one-step process which is much easier than the standard approach.

The usual method of converting between bases, is to work through base 10. We have ....

Staff - 4 years, 3 months ago

Yea, I think that was one of my problems on clarity. I realized that I didn't organize my article that well. I'll go add the fast way to the first example problem.

EDIT: also added the calculation for converting to base 10 then to the desired base.

- 4 years, 3 months ago

- 4 years, 3 months ago

Fixed the link (there was a weird semicolon in that url)

- 3 years, 12 months ago

you didn't fix it?

- 3 years, 12 months ago

Yes. This. +1 You are amazing.

- 4 years, 3 months ago

huh? this is screwed up. http://www.artofproblemsolving.com/Forum/viewtopic.php?f=721&t=566684

- 3 years, 11 months ago

I often resort to this technique in multiple-choice-questions and it saves a lot of time! Another great post!

- 4 years, 3 months ago

you are quite interesting! I .......think so.......

- 4 years, 1 month ago

This is a very fast method for conversion of bases

- 4 years, 3 months ago

Thanks a lot for shortcut method for answering quickly.

- 4 years, 3 months ago

Thanks a lot for sharing the trick ... :) ...

- 4 years, 3 months ago

I never knew this before, so yes thank you! The intense math section got a little messy but it was great; thanks for the post.

- 4 years, 3 months ago