Tower of Hanoi: 20 Discs, One Recursive Function, All 1,048,575 Moves

20 discs, one 4-line Python function, 1,048,575 moves, and every single one of them is legal. We climb from 1 disc to 20, and the move counter lands exactly. 0:00 Why do 20 discs take exactly 1,048,575 moves? 0:27 What is the fewest moves for 3 discs? 1:08 Why does one more disc double the moves? 2:31 How fast can every single move still be seen? 4:53 Which disc moves next? The binary secret 6:46 What shape do all the positions make? 8:01 How long would 15 to 19 discs take by hand? 8:36 Can we watch all 1,048,575 moves? 10:08 How long would the legend's 64 discs take? The Tower of Hanoi moves a stack of discs from peg A to peg C, one disc at a time, never a bigger disc on a smaller one. The recursive function on screen is the code that runs: to move n discs it moves n−1 out of the way, moves the biggest disc once and moves the n−1 back on top, so n discs take 2ⁿ − 1 moves. Move k always moves the disc given by the lowest 1 bit of k, so the moves count in binary, and all 3ⁿ positions form a Sierpinski triangle whose side is the fastest solution. Up to 11 discs every move gets its own frame; from 12 discs on the tower is a labelled time-lapse (the final tower slows back to every move at its start, its middle and its end), and the counter always shows the exact move. At one move per second, 20 discs would take 12 days, 3 hours and 16 minutes; the legend's 64 discs would take about 585 billion years. Original animation and sound by Rollody (@RollodyStudio). #towerofhanoi #recursion #python Rollody makes 2D simulations in code; subscribe to see more.