On this page
If you have ever played with a stack of wooden discs on three pegs, you know the basic rule: move the entire stack to another peg, one disc at a time, without ever placing a larger disc on a smaller one. The Tower of Hanoi is famous as a childhood toy and a classic computer science exercise. But the origins of the puzzle lie in the playful mind of a 19th-century mathematician.
Who invented the Tower of Hanoi puzzle?
The French mathematician Édouard Lucas invented the Tower of Hanoi in 1883. Lucas was an expert in number theory who loved recreational mathematics. When he first sold the game as a toy, he did not put his own name on the box. Instead, he claimed the puzzle was brought back from Tonkin (modern-day Vietnam) by "N. Claus (de Siam)". This exotic-sounding name was actually an anagram of "Lucas d'Amiens", a nod to his birthplace in Amiens, France.
The original instruction booklet carried a dramatic legend. It claimed that at a temple in the Indian city of Benares (Varanasi), priests were tasked with moving a Sacred Tower of Brahma. This divine tower consisted of 64 golden discs stacked on three diamond needles. The prophecy stated that when the priests finally moved the last disc into place according to the rules, the world would end.
How many moves does it take to solve the Tower of Hanoi?
The magic of the puzzle lies in its recursion. To move the largest disc at the bottom to the destination peg, you first have to move all the discs above it out of the way onto the spare peg. Then you move the largest disc. Finally, you move the smaller discs from the spare peg onto the largest disc.
The minimum number of moves to solve a tower of *n* discs is exactly 2ⁿ − 1. For a small puzzle with 5 discs, you can calculate the solution as 2⁵ − 1, which equals 31 moves. If you find yourself stuck on recursive formulas or exponential equations like these in your homework, the Fermi Problem Library has a step-by-step solver that explains the reasoning rather than printing an answer.
How do you solve the puzzle systematically?
If you try to move the discs at random, it is easy to get lost. However, there is a simple, repeating pattern that guarantees you will reach the solution in the minimum number of moves.
First, label your pegs: a starting peg, an auxiliary peg, and a destination peg. The direction you move the smallest disc depends on whether the total number of discs is odd or even:
For an even number of discs: Always move the smallest disc one peg to the right (looping back to the first peg if necessary).
For an odd number of discs: Always move the smallest disc one peg to the left.
On the next turn, make the only legal move that does not involve the smallest disc. Alternate between moving the smallest disc and making the other legal move, and the tower will perfectly assemble itself on the destination peg.
When will the priests finish the 64 discs?
The legend of the temple provides a perfect example of exponential growth. For 64 golden discs, the formula dictates 2⁶⁴ − 1 moves. That produces a staggeringly large number: 18,446,744,073,709,551,615 moves.
If the priests worked flawlessly, making exactly one move per second, they would need approximately 585 billion years to complete the task. This is roughly 42 times the current estimated age of the universe.
Mathematical ideas that scale this quickly can be difficult to picture. To visualise exponential growth and other abstract concepts interactively, you can experiment in the Fermi Simulation Lab.
What can we learn from Édouard Lucas today?
Lucas did much more than invent a toy. He proved that the massive number 2¹²⁷ − 1 is prime, a record that stood as the largest known prime for 75 years without the help of a computer.
When you encounter complex mathematical logic and feel overwhelmed, Fermi's AI tutor can help. The tutor teaches rather than answers: it holds a line of reasoning across a session, noticing where you are stuck, and building a plan for the session so you genuinely understand the underlying rules.
The Tower of Hanoi reminds us that the most profound mathematical laws are often hidden inside simple rules. By breaking a massive problem down into smaller, repeating steps, you can solve anything.
Read next:
