The Puzzle That Counts in Binary and Draws a Fractal

The oldest toy that still hides something

The three pegs in the console above hold a puzzle a five-year-old can play and a mathematician can spend an afternoon on. Move the whole stack from the first peg to the third. You may lift only the top disk of a peg, and you may never set a disk down on a smaller one. That is the entire rulebook.

Play it. With three disks it takes seven moves and you will find them quickly. Bump it to four and it takes fifteen; to five, thirty-one; to six, sixty-three. The pattern is already staring at you: the fewest moves to shift n disks is exactly 2 to the power n, minus one. Every disk you add roughly doubles the work, because to move the bottom disk at all you must first lift the entire tower above it out of the way, then move it, then rebuild the whole tower on top again. That is two copies of the smaller puzzle wrapped around one move of the biggest disk, and doubling is what recursion of that shape does.

The French mathematician Édouard Lucas sold the puzzle in 1883 wrapped in a legend: in a temple in Benares, priests are moving sixty-four golden disks between three posts under exactly these rules, and when they place the last disk the world ends. There is no need to book a flight. Sixty-four disks need 2 to the sixty-fourth minus one moves, which is 18,446,744,073,709,551,615 of them. At one move a second with no mistakes and no sleep, the priests finish in about 585 billion years, some forty times the current age of the universe. The doubling is the whole point of the story. It is also the first door into what the puzzle really is.

It counts in binary

Here is the first surprise, and Module 02 lets you scrub through it move by move. Number the moves of the perfect solution 1, 2, 3, and so on. Ask a simple question: on step number t, which disk moves?

You do not need to trace the puzzle to answer. Write t in binary, count the zeros hanging off its right-hand end, add one, and that is the disk. Step 1 is ...001, no trailing zeros, so the smallest disk moves. Step 2 is ...010, one trailing zero, so disk 2 moves. Step 4 is ...100, two trailing zeros, disk 3. The largest disk of an n-disk tower moves exactly once, on the single step whose number is 2 to the n minus one, dead in the middle of the solution.

This is called the ruler sequence, because it is the pattern of tick heights on a ruler: every half-inch mark is tall, every quarter-inch shorter, every eighth shorter still. The comb of bars in Module 02 is that ruler, and it is also the puzzle's move list. Look at what it says about effort. The smallest disk moves on every single odd step, which is half of all the moves. Disk 2 moves a quarter of the time, disk 3 an eighth, and so on down. Each disk moves 2 to the (n minus its rank) times, and those counts are the binary place values that add back up to 2 to the n minus one. The solution is not merely countable in binary. In a real sense it is the act of counting from 1 up to 2 to the n minus one, with each tick telling you which disk to nudge next.

There is an even simpler way to play perfectly that falls out of the same fact. On odd steps, always move the smallest disk, and always in the same direction around the three pegs. On even steps, make the only other legal move there is, since there is never more than one. Do that and you walk the optimal solution without ever thinking a move ahead. Watch the machine solve it in Module 01 and keep your eye on the smallest disk: it hops in one fixed rotation, tick, tick, tick, never pausing, and the rest of the puzzle organises itself around that heartbeat.

It draws a fractal

The second surprise is bigger, and it needs the whole map. Forget the single game for a moment and picture every legal arrangement of the disks at once. With n disks there are exactly 3 to the n of them, because each disk is on one of three pegs and any such assignment is a legal position. Draw one dot for every arrangement. Now connect two dots whenever a single legal move turns one position into the other.

You would expect a tangle. What you get, drawn for you in Module 03, is the Sierpinski triangle, the most famous fractal there is, assembled with no hand guiding it. The three sharp corners are the three tidy positions, every disk stacked on one peg. Near each corner sits a smaller triangle of positions that are one-away, two-away, and so on, and each of those is itself a smaller triangle of the same shape, all the way down. The self-similarity you saw in the ruler comb is the same self-similarity here, because it is the same recursion seen from a different side: a tower of n disks is three copies of a tower of n minus one, joined at their corners.

Play in Module 01 and the white dot in Module 03 is your current board. Every move you make is a single step to a neighbouring dot. The machine's perfect solve is a walk from one corner of the fractal to another, and that walk is lit up in gold. Here is the number that ties the whole drop together: the shortest path between two corners of this triangle is exactly 2 to the n minus one edges long, the very move count the game has been demanding since the first paragraph. The minimum number of moves is not a fact about disks at all. It is a distance across a fractal.

And notice the road it takes. You might guess the quickest way from one corner to another runs straight along the outer edge of the triangle. It does not. The shortest solve dives down through the middle of the gasket, threading the narrow bridges between the sub-triangles, which is exactly why the puzzle feels harder than a stack of rings has any right to feel. To move the tower you have to route through positions that look like backward steps, and the fractal shows you why: the direct road simply goes that way.

What the rules are

None of this was designed in. Lucas did not hide a fractal in a toy or encode binary in a legend. He wrote down three plain rules about disks and pegs, and the ruler sequence and the Sierpinski triangle were already inside them, waiting, the way the digits of pi are already inside a circle. The console recomputes all of it live as you play, from nothing but those rules: the move counts, the binary ticks, the 3-to-the-n dots and their gasket, the shortest road across it. Every number in this drop was checked offline first, the minimum moves against the recursion up to sixty-four disks, the ruler rule and the corner-to-corner distance against a direct search, so that what you are watching is a proof and not a picture of one.

That is the quiet lesson the toy keeps. A rule is never only what it says. It is everything that follows from it, all at once, and sometimes what follows is a fractal you can climb a stack of disks straight through the heart of.