Investigation: Faster Conversion through Bases

Before reading this, you may want to look over this article on Number Base Representation.


Let's start with a simple problem: Convert 10100111210100111_2 to base 44.

We first convert 10100111210100111_2 to base 1010, then convert that to base 44, as shown by the Number Base Representation article.

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

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

How many times does 43=644^3=64 go into 167167? 22 times. Now we multiply 22 by 6464 to get 128128, and subtract this from 167167 to get 3939.

How many times does 42=164^2=16 go into 3939? Twice, so we multiply 1616 by 22 to get 3232, and subtract that from 3939 to get 77.

How many times does 41=44^1=4 go into 77? 11 time, so we subtract 44 from 77 to get 33.

How many times does 40=14^0=1 go into 33? 33 times. Finally, our answer is 221342213_4.

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


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

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

We notice that in each little subdivision, the base 22 representation is automatically converted to the base 44 representation, independent of anything else! For example, 102=2410_2=2_4, 012=1401_2=1_4, and 112=3411_2=3_4.

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

101001112=1×27+0×26+1×25+0×24+10100111_2=1\times 2^7+0\times 2^6+1\times 2^5+0\times 2^4+0×23+1×22+1×21+1×200\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: 101001112=(1×27+0×26)+(1×25+0×24)+10100111_2=(1\times 2^7+0\times 2^6)+(1\times 2^5+0\times 2^4)+ (0×23+1×22)+(1×21+1×20)(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:

101001112=26(1×21+0×20)+24(1×21+0×20)+10100111_2=2^6(1\times 2^1+0\times 2^0)+2^4(1\times 2^1+0\times 2^0)+ 22(0×21+1×20)+20(1×21+1×20)2^2(0\times 2^1+1\times 2^0)+2^0(1\times 2^1+1\times 2^0)

Simplifying, we get that 101001112=2×43+2×42+1×41+3×4010100111_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 RHS\text{RHS} is exactly what a base 44 representation looks like! Therefore, we can clearly see that 101001112=2213410100111_2=2213_4.

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

We see that 102=2410_2=2_4, 102=2410_2=2_4, 012=1401_2=1_4, and 112=3411_2=3_4. Therefore our answer is 22134\boxed{2213_4}. You can see how much faster this is than to convert to base 1010, then back to base 44.

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


How about this problem: Convert 10100111210100111_2 to base 88.

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

Seeing that 23=82^3=8, let's try groupings of threes.

We try to group 10100111210100111_2 into groups of threes, but we can't, because there are 88 digits and 88 isn't divisible by 33. What do we do?

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

Now we can group as follows: 101001112    01010011110100111_2\implies 010|100|111.

Writing this out as the definition of a base number, we see that 101001112=(0×28+1×27+0×26)+10100111_2=(0\times 2^8+1\times 2^7+0\times 2^6)+(1×25+0×24+0×23)+(1×22+1×21+1×20)(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 101001112=2×26+4×23+7×2010100111_2=2\times 2^6+4\times 2^3 + 7\times 2^0.

Simplifying, we get that 101001112=2×82+4×81+7×80=247810100111_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:

102=2810_2=2_8, so the leftmost digit is 22.

1002=48100_2=4_8, so the middle digit is 44.

1112=78111_2=7_8, so the last digit is 77 and our final answer is 2478247_8.


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


Warning: Intense Math Ahead!

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

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

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

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

Now we group the digits into groups of xx each: (d1bnx1++dxb(n1)x)+(d_1b^{nx-1}+\cdots + d_xb^{(n-1)x})+(dx+1b(n1)x1++d2xb(n2)x)++(d_{x+1}b^{(n-1)x-1}+\cdots +d_{2x}b^{(n-2)x})+\cdots +(d(n1)x+1bx1++dnxb0)(d_{(n-1)x+1}b^{x-1}+\cdots +d_{nx}b^0).

Factoring each group, we get b(n1)x(d1bx1++dxb0)+b^{(n-1)x}(d_1b^{x-1}+\cdots +d_xb^0)+b(n2)x(dx+1bx1++d2xb0)++b^{(n-2)x}(d_{x+1}b^{x-1}+\cdots +d_{2x}b^0)+\cdots +b0(d(n1)x+1bx1++dnxb0)b^0(d_{(n-1)x+1}b^{x-1}+\cdots +d_{nx}b^0).

Changing b(ni)xb^{(n-i)x} to (bx)ni(b^x)^{n-i} for all i=1ni=1\rightarrow n, we get that (d1d2dnx)b=(bx)n1(d1bx1++dxb0)+(d_1d_2\cdots d_{nx})_b=(b^x)^{n-1}(d_1b^{x-1}+\cdots +d_xb^0)+(bx)n2(dx+1bx1++d2xb0)++(b^x)^{n-2}(d_{x+1}b^{x-1}+\cdots +d_{2x}b^0)+\cdots +(bx)0(d(n1)x+1bx1++dnxb0)(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 bxb^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 bb number to a base bxb^x number, i.e this trick will not work for converting a base 66 number into a base 33 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 bb number to a base bxb^x number, you will know a neat and fast trick to do so. (These occasions happen frequently in competition math.)


Problems

*1. * Convert 12321412321_4 to base 1616.

*2. * Convert 1120100324112010032_4 to base 88. Hint: do an intermediate conversion first.

*3. * Convert 12345678912345678_9 to base 33.

*4. * Prove the formula for converting a base bxb^x number to a base byb^y number.

Note by Daniel Liu
5 years, 10 months ago

No vote yet
2 votes

  Easy Math Editor

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.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 1

paragraph 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×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

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

Daniel Liu - 5 years, 10 months ago

Log in to reply

Thank you Daniel! It was great :)

Happy Melodies - 5 years, 10 months ago

Log in to reply

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

Convert (1234567)8 (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 ....

Calvin Lin Staff - 5 years, 10 months ago

Log in to reply

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.

Daniel Liu - 5 years, 10 months ago

Log in to reply

To learn the very basics, see This Article

Akshaj Kadaveru - 5 years, 10 months ago

Log in to reply

Yes. This. +1 You are amazing.

Daniel Liu - 5 years, 10 months ago

Log in to reply

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

David Lee - 5 years, 6 months ago

Log in to reply

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

David Lee - 5 years, 6 months ago

Log in to reply

you didn't fix it?

Daniel Liu - 5 years, 6 months ago

Log in to reply

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

Mursalin Habib - 5 years, 10 months ago

Log in to reply

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.

Justin Wong - 5 years, 10 months ago

Log in to reply

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

Kiran Dey - 5 years, 10 months ago

Log in to reply

Thanks a lot for shortcut method for answering quickly.

Sunil Pradhan - 5 years, 10 months ago

Log in to reply

This is a very fast method for conversion of bases

Rohit Nair - 5 years, 10 months ago

Log in to reply

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

Archiet Dev - 5 years, 7 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...