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.
- 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.
- 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.
- 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.
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.
