## The Towers of Hanoi

A set of colorful, cascading disks stacked on a peg. What could easily double as a child’s toy also serves as an ancient mathematical puzzle, the Towers of Hanoi. Often used to teach recursive problem solving strategies, the puzzle poses a simple challenge—to move the stack of disks from the leftmost peg to the rightmost peg one disk at a time with one restriction: a disk cannot be placed on top of a smaller disk.

Take a moment to familiarize yourself with the puzzle by playing around with this online version. Setting the number of disks to 3 is a great place to start.

It may be surprising that, no matter how many disks there are, this problem is always solvable with just three pegs. Even more surprising, the optimal solution for any number of disks (the solution that requires the fewest number of moves) directly mirrors the rhythm of counting in binary.

Before diving into this optimal solution (in a later article), this article focuses on understanding what counting in binary looks like and explores the nature of different number systems.

## Base-10

The number system we most commonly use involves counting in base-10, a natural choice given the number of fingers we have on our hands. Consider the number **104** for example. Let’s index the digits from right to left, beginning with zero:

- the value at index 0 is
**4**, - the value at index 1 is
**0**, - and the value at index 2 is
**1**.

Because we are working in base-10, there are 10 possible values for each digit (0, 1, 2, 3, 4, 5, 6, 7, 8, or 9) and each index represents a consecutively larger power of 10 corresponding to its index. The number **104** can be expressed as the sum of powers of **10** as follows:

- 10^0 *
**4**(or**4**ones) - 10^1 *
**0**(or**0**tens) - 10^2 *
**1**(or**1**hundred).

## Base-2

Let’s now consider how this same value would be written in a different base: base-2, or binary. The binary system has only 2 possible values for each digit (0 or 1) and is most useful in the field of computer science as it is easy to consider an electrical component as having one of two possible states (on or off). In the binary representation of a number, each index represents a consecutively larger power of 2 corresponding to its index.

After some calculation, we can express **104** as the sum of powers of **2** as follows:

- 2^0 *
**0**(or**0**ones) - 2^1 *
**0**(or**0**twos) - 2^2 *
**0**(or**0**fours) - 2^3 *
**1**(or**1**eight) - 2^4 *
**0**(or**0**sixteens) - 2^5 *
**1**(or**1**thirty-two) - 2^6 *
**1**(or**1**sixty-four)

Thus, the binary representation of **104** is **1101000**.

## Converting Between Bases

To round out this introduction to different counting systems, let’s actually go through the process of converting a value from one base to another.

Consider the base-10 value **2643**. Although base-10 is standard, it is good practice to break apart the digits and understand how this value is written. From right to left, we have:

- 10^0 *
**3**(or**3**ones) - 10^1 *
**4**(or**4**tens) - 10^2 *
**6**(or**6**hundreds) - 10^3 *
**2**(or**2**thousands)

Now we will determine how to express **2643** in base-8 by recursively answering the same question:

- What is the largest power of
**8**less than or equal to**2643**?- The answer is 8^3 = 512, and we can fit
**five**512s into 2643 with 83 left over.

- The answer is 8^3 = 512, and we can fit
- What is the largest power of
**8**less than or equal to**83**?- The answer is 8^2 = 64, and we can fit
**one**64 into 83 with 19 left over.

- The answer is 8^2 = 64, and we can fit
- What is the largest power of
**8**less than or equal to**9**?- The answer is 8^1 = 9, and we can fit
**two**8s into 19 with 3 left over.

- The answer is 8^1 = 9, and we can fit
- What is the largest power of
**8**less than or equal to**1**?- The answer is 8^0 = 1, and we can fit
**three**1s into 3 with 0 left over.

- The answer is 8^0 = 1, and we can fit

Putting it all together, from right to left, we have:

- 8^0 *
**3**(or**3**ones) - 8^1 *
**2**(or**2**eights) - 8^2 *
**1**(or**1**sixty-four) - 8^3 *
**5**(or**5**five-hundred twelves)

Thus, the base-8 representation of **2643** is **5123**.

## The Value 10

One interesting tidbit about working across different number systems is how different values are represented by **10**. In any arbitrary base-**n **system, the value **10** can be read as:

- n^0 *
**0**(or**0**ones) - n^1 *
**1**(or**1**n)

Thus, in any base-**n** system, the value of **10** is exactly **n**. To get a bit existential, every number system is, to itself, base-10.