From Tower of Hanoi to Counting Bits
Tower of Hanoi
A few weeks ago, I watched Rise of the Planet of the Apes. The movie showed a genetically engineered chimpanzee trying to solve a puzzle involving four discs, initially stacked in ascending order of size on one of three pegs. The chimpanzee was supposed to transfer the entire stack to one of the other pegs, moving only one disc at a time, and never placing a larger disc on a smaller one.
The problem was called the Lucas' Tower in the movie. I
have always known this problem as the Tower of Hanoi
puzzle. The minimum number of moves required to solve the problem
is
Referring to the problem as the Lucas' Tower made me wonder why it was called so instead of calling it the Tower of Hanoi. I guessed it was probably because the puzzle was invented by the French mathematician Édouard Lucas. Later when I checked the Wikipedia article on this topic, I realised I was right about this. In fact, the article mentioned that there is another version of this problem known as the Tower of Brahma that involves 64 discs made of pure gold and three diamond needles. According to a legend, a group of Brahmin priests are working at the problem and the world will end when the last move of the puzzle is completed. Now, even if they make one move every second, it'll take 18 446 744 073 709 551 615 seconds to complete the puzzle. That's about 585 billion years. The article also had this nice animation of a solution involving four discs.

I'll not discuss the solution of this puzzle in this blog post.
There are plenty of articles on the web including the Wikpedia
article that describes why it takes a minimum of
Binary Numbers
If we denote the minimum number of moves required to solve the Tower
of Hanoi puzzle as
While playing with different values of
Assumptions
Before proceeding to the problem, let us define the bit-length of an integer to eliminate any possibility of ambiguity:
-
A positive integer
is said to be an -bit integer if and only if the minimum number of bits required to express the integer is or equivalently,
We will be dealing with arbitrary precision integers (bignums) in the problem, so let us also make a few assumptions:
-
Addition or subtraction of an
-bit integer and an -bit integer ( ) takes time. -
Counting the number of
-bits in an -bit integer takes time.
The definition along with the assumptions lead to the following conclusions:
-
Adding or subtracting two integers
and takes time. -
Counting the number of
-bits in an integer takes time.
Binary Puzzle
The naive approach involves adding all the
We can arrive at a much more efficient solution if we look at what
the binary representation of the sum looks like. We first arrive at
a closed-form expression for the sum:
If we use the notation
What would have taken 2 exbibytes and 1 bit of memory with the naive approach requires 8 bytes and 1 bit of memory now.