Move a stack of disks from one peg to another, never putting a big disk on a small one. The solution is the purest recursion there is — move the top n−1 aside, move the biggest, move the n−1 back — and it is exactly the shape I-13 is best at. A rare dart where the wall is not I-13’s; it is f64’s.
THE TECHNIQUE move n−1, move 1, move n−1
To move n disks A→C: first move n−1 disks A→B (recursively), move the biggest A→C, then move n−1 disks B→C. It always takes exactly 2n−1 moves — provably minimal. Watch it solve itself. live demo
4
HISTORY & CREDIT a toy, a pseudonym, and the end of the world
Often told as an ancient Hindu legend — it is a Victorian invention with a legend attached as marketing. cited
1883 · Édouard Lucas, French number theorist, invents and sells it as a puzzle under the anagram pen-name “N. Claus de Siam” (= Lucas d’Amiens). the legend · priests in a temple at Benares move 64 golden disks; when the last move is made, the world ends. At one move a second that is 264−1 ≈ 585 billion years — longer than the universe has existed. Lucas · also gave us the Lucas numbers and a primality test still used on Mersenne primes — and died from a freak dropped-plate wound at a banquet.
The disks are a toy; the recursion is eternal. Every CS student meets it, because nothing shows self-reference more cleanly. canonical
RECOMMEND FOR I-13 its home turf — the wall is f64’s
I-13 has no loop; iteration is recursion, so Hanoi is native. The minimal move count runs exactly:
def moves(I n) {
if n == 0 { -> 0 }
-> 2 * moves(n - 1) + 1
}
I h20 <- moves(20)
But the temple’s 64 disks overflow f64’s exact range: 2⁶⁴−1 > 2⁵³, so the last digits are lost:
moves(64) computes, but 18446744073709552000 != the true 18446744073709551615
(f64 has only ~15-16 exact digits; the recursion is fine, the NUMBER is too big)
Recommend: again the withheld one — arbitrary-precision integers — and Hanoi is the gentlest possible argument for it: the algorithm is perfect and I-13-native, only the counting exceeds f64. No new control, no new alphabet; just an exact integer type, if and when the author decides the corpus wants one. Otherwise: a clean no-wall celebration — recursion with a depth bound is exactly what I-13 was built to make honest.