# 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
6 years, 11 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

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

- 6 years, 11 months ago

Thank you Daniel! It was great :)

- 6 years, 11 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 - 6 years, 11 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.

- 6 years, 11 months ago

- 6 years, 11 months ago

Yes. This. +1 You are amazing.

- 6 years, 11 months ago

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

- 6 years, 6 months ago

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

- 6 years, 7 months ago

you didn't fix it?

- 6 years, 7 months ago

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

- 6 years, 11 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.

- 6 years, 11 months ago

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

- 6 years, 11 months ago

Thanks a lot for shortcut method for answering quickly.

- 6 years, 11 months ago

This is a very fast method for conversion of bases

- 6 years, 11 months ago

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

- 6 years, 8 months ago