Waste less time on Facebook — follow Brilliant.
×

Number Base Representation

When learning to count, we were taught the digits \( 0, 1, 2, 3, 4, 5, 6, 7, 8, \) and \(9\). We were told that the next number in the sequence is \(10\), which consists of the digit \(1\) written next to \(0\). This is the Hindu-Arabic numeral system, which represents a number using the place-value notation. The number \( 321\) is interpreted as \( 3 \times 10^2 + 2 \times 10^1 + 1 \times 10^0 \). These calculations are done in base 10, which is partially explained by having 10 fingers (including thumbs) which we use to count.

The use of place-value notation in base 10 is not standard throughout history. In fact, many of the great historical civilizations used their own form of number systems. For example, the Babylonains used a sexagesimal (base 60) numeral system, which allowed them to simply represent several fractions. Due to their influence, we now have 60 seconds in a minute, 60 minutes in an hour, and 360 degrees in a circle.

How does number base representation work? The base is the number of unique digits (including zero), which are used in the representation. In this post, \( (X)_b \) will denote the number \(X\) in base \(b\). If a base is not given, it is assumed to be 10.

Suppose that Brilli the ant uses a base 6 system, as she has 6 legs for counting. What would the number \( (321)_6 \) mean to us?

Working from the right, we see that there is 1 unit of \( 6^0 = 1 \), and then \(2\) units of \(6^1=6 \), and finally 3 units of \( 6^2 \). Hence, we can calculate that

\[ (321)_6 = 3 \times 6^2 + 2 \times 6^1 + 1 \times 6^0 = 121.\]

More generally, we can convert a number in base \(b\) into our decimal system via

\[ (b_n b_{n-1} \dots b_1 b_0 )_b = b_n \times b^n + b_{n-1} \times b^{n-1} + \ldots + b_1 \times b^1 + b_0 \times b^0. \]

How do we reverse this process? What would our number \( (321)_{10} \) mean to Brilli the ant? We need to find numbers \( b_i \), each taking value \(0, 1, 2, 3, 4\) or \(5\). It can be tedious to guess and check, so we use the following algorithm. We start by performing division by \(b\), and record the remainder. We then take the dividend and divide that by \(b\) again, and record the remainder. This process continues till the dividend is finally 0. We then read the remainders that have been obtained. As an explicit example, to calculate \( 321\) in base 6, we perform the steps:

\[ \begin{array}{l | lll} 321 & 321& = 53 \times 6 &+ 3\\ 53 & 53 &= 8 \times 6 &+ 5 \\ 8 & 8 &= 1 \times 6 &+ 2 \\ 1 & 1 &= 0 \times 6 &+ 1 \\ \end{array} \]

As such, the algorithm tells us that \( (1253)_6 = 321 \).

Worked Example

1. Convert \( (123)_9 \) into base 3.

Solution: We will work through base 10. First, we convert \((12345)_9 \) into base 10. From the above, we know that

\[ (123)_9 = 1 \times 9^2 + 2\times 9^1 + 3 \times 9^0 = 102.\]

Next, we use the algorithm to convert to base 3.

\[ \begin{array} {l | lll} 102 & 102 & = 34 \times 3 &+ 0 \\ 34 & 34 & = 11 \times 3& + 1\\ 11 & 11 & = 3 \times 3 &+ 2 \\ 3 & 3 & = 1\times 3 &+ 0 \\ 1 & 1 & = 0 \times 3 & + 1. \\ \end{array} \]

Hence \( (10210)_3 = 102 = (123)_9 \).

 

2. Why does this algorithm to convert into base \(b\) work?

Solution: Suppose we want to convert a number \(N\) into base \(b\). If \(N = (b_n b_{n-1} \ldots b_1 b_0 )_b\), then we know that \[ N - b_0 = b ( b_n \times b^{n-1} + b_{n-1} \times b^{n-2} + \ldots + b_1 \times b^0 ) \] is a multiple of \(b\). But since \( 0 \leq b_0 < b \), this tells us that \(b_0\) must be the remainder when \(N\) is divided by \(b\).

We are now interested in \( \frac{ N - b_0} { b} \). Similarly, we obtain that \( b_1\) must be the remainder when \( \frac{N-b_0} { b} \) is divided by \(b\). We repeat this process till we terminate at \(0\).

Note by Arron Kau
3 years ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

Awesome n cool note!!! Opi Dipto · 2 years, 2 months ago

Log in to reply

Cool note!!! Yash Singhal · 2 years, 5 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...