Different bases

In this post I'm going to talk about writing numbers in different bases.

Our usual way of writing numbers is in base 10. This means we represent a number as a sum of multiples of powers of 10. For example,

$$\begin{align*} 324 &= 300 + 20 + 4\\ &= 3\cdot100 + 2\cdot 10 + 4\cdot1\\ &= \mathbf 3\cdot10^2 + \mathbf 2\cdot 10^1 + \mathbf 4\cdot10^0 \end{align*}$$

Writing numbers in another base means we replace 10 with some other number. For example, $13$ is written as $1101$ in binary (base 2), because

$$\begin{align*} 13 &= 8 + 4 + 1\\ &= 1\cdot8 + 1\cdot4 + 0\cdot2 + 1\cdot1\\ &= \mathbf 1\cdot2^3 + \mathbf 1\cdot2^2 + \mathbf 0\cdot2^1 + \mathbf 1\cdot2^0 \end{align*}$$

We can indicate the base with a subscript: $13_{10} = 1101_{2}$. Note we're still using base 10 to write the subscript.

If the base is bigger than 10, we need symbols to go beyond the existing digits $0,1,2,3,4,5,6,7,8,9$. Traditionally, this is done using letters. So for instance, A represents 10, B represents 11, and so on, and F represents 15. For example, $173$ in "hexadecimal" (base 16) is $\mathrm{AD}_{16}$, because

$$\begin{align*} 173_{10} &= 10\cdot 16 + 13\cdot 1\\ &= \mathbf A\cdot16^1 + \mathbf D\cdot16^0 \end{align*}$$

How many words can you spell in hexadecimal? What are their decimal values? For example, $\mathrm{BEEF}_{16}=48,879$.

Here's a demo so you can see how this works with different numbers:

Source

There's no mathematical reason to choose 10 as our base, it's just a cultural convention (probably due to us having ten fingers). For example, the Babylonians used base 60 ("sexagesimal"), and the Mayans used base 20 ("vigesimal"). Hexadecimal is used fairly often in computing.

The same idea works to the right of the "decimal point". For instance, $0.75_{10} = 0.11_{2}$, because

$$\begin{align*} 0.75_{10} &= 0.5 + 0.25\\ &= \mathbf 1\cdot 2^{-1} + \mathbf1 \cdot{2^{-2}} \end{align*}$$

Converting

Example

Let's see how to convert bases by hand. We'll write $\red{420}$ in base $\blue{16}$. The remainder when $\red{420}$ is divided by $\blue{16}$ is $\green4$, which we write as $\red{420}\equiv\green4\bmod\blue{16}$. This tells us that the last hexadecimal digit of $\blue{16}$ is $\green4$.

Next, $\red{420}-\green4=\red{416}$ is divisible by $\blue{16}$. We divide $\red{416}$ by $\blue{16}$ to get $\frac{\red{416}}{\blue{16}}=\red{26}$. Now we have $\red{26}\equiv\green{10}\bmod\blue{16}$, so the second-last ("tens") hexadecimal digit of $\red{420}$ is $\green{\mathrm A}$ (which we use for the number $\green{10}$).

Again we subtract $\red{26}-\green{10}=\red{16}$, which divided by $\blue{16}$ is $\green1$. So $\red{420}$ in hexadecimal is $\red{420}_{10} = \green{\mathrm{1A4}}_{\blue{16}}.$ Again, remember that this means $\red{420} = \green4\cdot\blue{16}^0 + \green{10}\cdot\blue{16}^1 + \green1\cdot\blue{16}^2 \fade{{}+\green0\cdot\blue{16}^3+\dotsb}$ The algorithm we used above basically works by writing this as $\red{420} = \green4\cdot\blue{16}^0 + \blue{16}\cdot(\green{10} + \blue{16}\cdot(\green1\fade{{} + \blue{16}\cdot(\green0 + \dotsb)})).$

Here's an implementation of that in code. We can check our work against the built-in Number.prototype.toString() method.

Can you modify the above algorithm to handle decimals, e.g. $420.1137$?

Uses

Although the vast majority of what we do is in base 10, there are a handful of places where we make use of other bases. Here are a few:

Colors

If you grew up in the 90s, you may remember [color=#FF0000] or <FONT COLOR="#ffffff"> from forums and GeoCities. What do these mean?

On a computer, colors are represented by red, blue, and green (RGB) components, each between $0$ and $255$. Since $255 = 256 - 1 = 2^8 - 1 = 100_{16}-1$, this is between $0$ and $\mathrm{FF}_{16}$ when written in hexadecimal. For example, #FF0060 is $255$ red, $0$ green, and ${60}_{16}=96$ blue. Here's a demo where you can experiment with this in general:

Source

URLs

Very high bases are sometimes used to make short URLs, e.g. https://old.reddit.com/11jznte/ or https://youtu.be/dQw4w9WgXcQ. In their database, this thread has some numeric ID like 1298482891, and 11jznte is that number written in some base. I'm not sure exactly which base they chose: if we use capital and lower letters, the digits 0–9, and hyphens and underscores, then we get $2\cdot26 + 10 + 2 = 64$ as a base. But it's best to omit e.g. capital O and lowercase l, so we don't get confused between 0O1l, so in practice it's more likely to be base 62 or smaller.

What does it mean?

So, a given number can be represented many different ways. What can we learn about a given number by writing in various different bases? Let's look at a few different examples of this, and then a conceptual way of organizing it.

Rationality

We have names for different kinds of numbers.

• the natural numbers are $0,1,2,\dots$
• the integers are $\dots,-2,-1,0,1,2,\dots$
• a rational number is one that can be expressed as a ratio of integers. For example, $\frac12$, $\frac53$, $-\frac{12}7$, and so on.
• numbers which aren't rational are called irrational. For example, $\pi$ and $\sqrt2$ are irrational.

Rationality can be seen in the digit representation of a number: a rational number will always have a repeating pattern of digits. For example,

$$\begin{align*} \frac{4}{11} &= 0.36363636\dots\\ \end{align*}$$

which we write as

$$\begin{align*} \phantom{\frac{4}{11}} &= 0.\overline{36}\phantom{363636\cdots} \end{align*}$$

This includes the case of a terminating expression, which we can think of as a repeating $0$. In fact, every rational number has a terminating expression in some base. For example, we have $11/9 = 1.\overline2_{10} = 1.12_6 = 1.02_3.$ which terminates in bases 3 and 6 but repeats infinitely in base 10.

Irrational numbers, on the other hand, never fall into a repeating pattern. (This doesn't mean there's "no pattern" to their digits, just that it can't be expressed so simply.)

Last digits

Let's start by thinking about what the last digit of an integer written in binary means. The numbers $0$ through $7$ written in binary are $\blue0,\, \red1,\, 1\blue0,\, 1\red1,\, 10\blue0,\, 10\red1,\, 11\blue0,\, 11\red1$ Notice that: the last binary digit of a number tells us whether it's odd or even!

In many situations, this is all we need to know about the number. For example, suppose you leave a room with the lights on, and come back later and the lights are off. You know that the light switch must have been flipped an odd number of times, but the exact number of times isn't relevant.

In general: the last digit of a number in base $b$ is its remainder when divided by $b$.

What about, say, the first digit? It turns out that this is harder to interpret. To see why, let's consider two addition problems, where some of the numbers are covered up.

$$\begin{align*} ?7\\ {}+{?4}\\\hline ??1 \end{align*} \qquad \begin{align*} 7?\\ {}+{2?}\\\hline ??? \end{align*}$$

For example, the first of these could be either of the concrete problems

$$\begin{align*} 37\\ {}+64\\\hline 101 \end{align*} \qquad \begin{align*} 17\\ {}+24\\\hline 41 \end{align*}$$

Although these give different answers, the last digit is the same between the two answers. But in the second case, we can't pin down any of the digits for sure, not even the tens. For example, we could have either of

$$\begin{align*} 73\\ {}+25\\\hline 98 \end{align*} \qquad \begin{align*} 75\\ {}+29\\\hline 104 \end{align*}$$

At most we can say that the middle $?$ is either $9$ or $0$.

In other words: to figure out the last digit of $a+b$, you just need to know the last digit of $a$ and of $b$. But to know the second-last digit of $a+b$, you need to know the last two digits of $a$ and $b$, since there could be carries from the last digit.

Knowing the last $k$ digits of a number written in base $b$ is the same as knowing its remainder when divided by $b^k$.

How do different bases relate? Let's write the last digits of the numbers $0$ through $9$ in bases $2$, $5,$ and $10$.

Notice that: knowing the last digit of $n$ in base $10$ is the same as knowing its last digit in base $2$ and in base $5$!

Let's try this for $2$ and $4$:

Here we don't have quite the same pattern as above: knowing the last digit in base $4$ isn't the same as "knowing the last digit in base $2$ and also in base $2$." Instead, knowing the last digit of $n$ in base $4$ is the same as knowing its last two digits in base $2$.

If $b$ and $c$ have no factors in common, then knowing the last however many digits in base $bc$ is the same as knowing the last that many digits in bases $b$ and $c$.

At the opposite end, knowing the last $k$ digits in base $b^r$ is the same as knowing the last $rk$ digits in base $b$.

Example

Let's take $b=360$. The prime factorization of this is $360=2^3 \cdot 3^2 \cdot 5$. Thus, to know the last $2$ digits of a number in base $360$ is the same as knowing

• its last $6$ digits in base $2$, i.e. its remainder when divided by $2^6=64$;

• its last $4$ digits in base $3$, i.e. its remainder when divided by $3^4=81$;

• its last $2$ digits in base $5$, i.e. its remainder when divided by $5^2=25$.

The function analogy

Writing a number in base $b$, $n = n_0 b^0 + n_1 b^1 + n_2 b^2 + \dotsb$ looks very similar to writing a polynomial in one variable $x$: $f(x) = a_0 x^0 + a_1 x^1 + a_2 x^2 + \dotsb$

For example, the number $4,321 = 1 + 2\cdot 10 + 3\cdot10^2 + 4\cdot10^3$ looks very similar to the polynomial $f(x) = 1 + 2x + 3x^2 + 4x^3.$ In particular, $4,321=f(10)$.

So, is it possible to either view

• polynomials as "numbers in base $x$", or alternatively
• integers as "functions in the variable $b$"?

The main difference between the two situations is that to add two polynomials, you just add the coefficients together:

$$\begin{align*} &{}\phantom= (1+2x+3x^2+4x^3) + (5+9x+6x^2+x^3)\\ &= (1+5) + (2+9)x + (3+6)x^2 + (4+1)x^3\\ &= 6 + 11x + 9x^2 + 5x^3 \end{align*}$$

but when adding two numbers, we have to carry:

$$\begin{align*} 4,321 + 1,695 &= (1+5) + (2+9)\cdot10 + (3+6)\cdot10^2 + (4+1)\cdot10^3\\ &= 6 + \red11\cdot10 + 9\cdot10^2 + 5\cdot10^3\\ &= 6 + 1\cdot10 + \red10\cdot10^2 + 5\cdot10^3\\ &= 6 + 1\cdot10 + 0\cdot10^2 + 6\cdot10^3\\ &= 6,016 \end{align*}$$

So in this analogy, polynomials are actually easier to work with than numbers! So we should take the second of the above suggestions: that is, try to understand integers as ``functions in the variable $b$''.

There's a ton of math research around trying to flesh out this analogy; it broadly goes under the name of the "function analogy" or the "philosophy of the field with one element" (but it will take quite a while to explain that name). The stuff I think about is part of or adjacent to one of the main approaches to doing so (but there are several others). Basically, we understand polynomials very very well, so we could try to take the tools we have for working with polynomials and translate them through this analogy to get very powerful tools for understanding integers and prime numbers and so on.

Carrying is just one way that base expansions are harder to work with than polynomials. Another major one is that we can contemplate polynomials in multiple variables, e.g.

$$x^2 + 2xy + y^2 \quad\text{or}\quad z^2-xy$$

We really don't know what the analogue of this would be for numbers, i.e. how to "mix bases". In the past 10 years, there's been an explosion of activity in this area, and we now have very precise glimpses of parts of what this ought to be. These are very exciting, but we definitely don't have the full picture yet.

What would be a satisfactory answer to "fleshing this out"? And relatedly, what would such a thing be good for?

The Riemann hypothesis is widely considered the most important unsolved problem in math. It's a technical statement about complex numbers, but basically it gives an extremely precise description of the distribution of prime numbers, i.e. what is the probability that a randomly chosen number will be prime? There's a "polynomial" version of the Riemann hypothesis, which is still extremely difficult, but was proven in 1974. So one proposed strategy for proving the original Riemann hypothesis is to take that proof and translate it through this analogy—but that gets stuck due to not being able to talk about "multi-base numbers".

Conversely, this provides a way of assessing claims of "making sense of the function analogy". There's lots and lots of ideas about how to do this—but until we can prove the Riemann hypothesis, we haven't found the "one true way" (if there is one).

I'll devote a future chapter to explaning the function analogy in more detail.