# Tower of Hanoi

**Type:** Concept  
**Domain:** Recreational Mathematics  
**Invented:** 1883, Édouard Lucas  
**Codex URL:** /mathematics/recreational/tower-of-hanoi/  
**Entry status:** Live — v1.0 (2026-05-27)

## Summary
Puzzle requiring exactly 2ⁿ−1 moves for n disks. Classic example of recursion and exponential growth.

## Rules
Move stack of disks between 3 pegs: move one disk at a time; never place larger disk on smaller.

## Formula
T(n) = 2ⁿ−1. For 64 disks (the legend): 2⁶⁴−1 ≈ 18.4 quintillion moves ≈ 585 billion years at 1/second.

## Recursive solution
1. Move n−1 disks A→B (recursive)
2. Move largest disk A→C
3. Move n−1 disks B→C (recursive)

Recurrence: T(n)=2T(n−1)+1, T(0)=0 → T(n)=2ⁿ−1 (proven optimal, not just achievable).

## Binary connection
Move k's disk determined by lowest-set bit position in binary representation of k.

## Frame-Stewart conjecture (4+ pegs)
Proposed 1941; proven optimal only in 2014 (Bousch) — 73 years as open conjecture.

## Sources
### Tier 1
- Graham, R.L., Knuth, D.E. and Patashnik, O. (1994). *Concrete Mathematics*. 2nd ed.
### Tier 2
- Hinz, A.M. et al. (2018). *The Tower of Hanoi — Myths and Maths*. 2nd ed.
- Bousch, T. (2014). La quatrième tour de Hanoï. *Bull. SMF*.

---
*Mathematics Codex entry v1.0 — added 2026-05-27 — thecodex.expert/mathematics/*