Tower of Hanoi (1883) — The 64 Disks That Never End, and the Legacy of Recursion

Introduction

This is a toy from 1883. Three pegs stand upright; on one of them sit disks of differing size, the largest at the bottom, stacked in order. The rules are just two: move only one disk at a time, and never place a larger disk on a smaller one. Under that constraint, transfer the whole tower to another peg. That single act still survives, under the name 'Tower of Hanoi,' in classrooms and toy boxes the world over.

Its appearance is utterly plain — wooden pegs and a few rings. A child learns the rules in a minute. Yet I take this toy up as an object of history because, beneath that plainness, the very structure that computer science would later call 'recursion' was already embedded in finished form. As early as 1883, people held that structure in their hands as a thing they could touch.

This essay traces the identity of the mathematician who invented the tower, the grand fiction he draped over it, and the weight of the number 2^n−1 that follows from its simple rules. Not out of nostalgia, but to confirm how very old the source is for ideas — 'nesting,' 'state space' — that modern puzzles use as a matter of course.

Three pegs and a golden tower — a toy of 1883 (illustration, AI-generated)

The Context of Its Time

Paris, 1883. The inventor was the mathematician Édouard Lucas (1842–1891). But when the toy appeared, its author was given as 'N. Claus (de Siam), professor at the Li-Sou-Stian College.' This was misdirection. 'N. Claus (de Siam)' is an anagram of 'Lucas (d'Amiens),' and 'Li-Sou-Stian' is a rearrangement of the Lycée Saint-Louis, the prestigious Paris school where he was then teaching. The trick was unmasked early by the science writer Henri de Parville.

Lucas did not build the toy as a mere pastime. He was a serious number theorist, remembered for the 'Lucas sequence' and the 'Lucas–Lehmer test.' Europe then had a rich tradition of récréations mathématiques — conveying the properties of numbers through play — and the Tower of Hanoi sits squarely within that lineage. The tower is included in Lucas's own work of that name.

A grand story accompanied the toy. It was said that in a temple at Benares (today's Varanasi), priests endlessly moved 64 golden disks across three diamond needles under these same rules, and that when the tower was complete the world would crumble to its end. A fabrication, of course. But I do not make light of this embellishment. The gesture of lending mythic weight to the coldness of number is the very prototype of the 'staging' that later puzzle authors would study again and again.

A boxed game and a slip bearing the pseudonym — the era's backdrop (illustration, AI-generated)

Mechanics

The rules are unchanged since 1883. One disk at a time. Never a larger disk atop a smaller one. The empty peg may be used freely. Those three points alone define the task of moving the tower. Touch it and within minutes you can 'sort of' shift the disks; but the instant you care about the fewest moves, a structure rises into view.

That structure is recursion. Suppose you want to move an n-disk tower from A to C. Then move the top n−1 disks aside to B, move the single largest disk from A to C, and finally move the n−1 disks from B to C. The problem decomposes into two copies of the same problem one size smaller. The move count T(n) satisfies T(n) = 2·T(n−1) + 1, and solving this gives exactly T(n) = 2^n−1. One disk, one move; three disks, seven; ten disks, 1023. The shortest solution is not unique, but the minimum move count is fixed completely by this formula.

Here we return to the legend. For 64 disks the count is 2^64−1, roughly 1.8×10^19 moves. Even if a priest moved one disk per second without rest, it would take about 585 billion years — some 42 times the current estimated age of the universe. The threat that 'the tower will not be finished until the world ends' is, in other words, the immensity of an exponential translated into the language of myth. From simple rules an explosive number is born. That gap is the very core of the pleasure that thinking-puzzles still sell today.

Recursive decomposition and its consequence, 2ⁿ−1 (illustration, AI-generated)

Lineage Into the Present

Where the 1883 toy struck its deepest roots was twentieth-century computer science. The Tower of Hanoi has become an almost standard subject for teaching recursion in programming. Few examples embody the recursive idea — 'call yourself, one size smaller' — so perfectly in so few rules. At the same time, the tower is the clearest teaching aid for the view called 'state space,' in which every configuration is a point and every legal move an edge.

I regard this 'state space' view as a key for reading modern puzzles. See the totality of configurations as one vast maze and trace the shortest path through it: the analysis of Sokoban and the solvability of sliding puzzles both stand on this view. What the Tower of Hanoi gave in 1883 was less the toy itself than a pair of spectacles — a way of looking at thinking-puzzles.

As a modern example that makes nesting itself the play, I read 2022's Steam release 'Patrick's Parabox' as an extension of this lineage. A box inside a box, and a box that may contain itself — this is a puzzle that places recursion at the very center of its rules. The author has not, of course, testified to taking direct inspiration from the Tower of Hanoi. But the skeleton — 'the same problem, shrunk, nested within itself' — is what the wooden tower of 1883 had already shown in a form one could touch. Lineage is not a deed of influence; it is the recurrence of the same skeleton across eras.

From the golden tower to a nested present (illustration, AI-generated)

References

Sources referenced in this article:

・Wikipedia: Tower of Hanoi

・Wikipedia (Japanese): Tower of Hanoi

・Wikipedia: Édouard Lucas

・College of William & Mary: The Tower of Hanoi

・Scientific American: The Tower of Hanoi

Closing

The tower at Benares is still moving, within its legend. The final move, 585 billion years away, has naturally never once been made. Yet that very endlessness, I think, is the essence of what the toy showed in 1883: simple rules, and a move count that swells exponentially from them. Within a finite tool you can hold in your hand, an infinity no human life could traverse is folded away.

Historically, what the Tower of Hanoi left behind is not any particular solution. It is the recursive idea itself — that a problem can be decomposed into smaller copies of itself. That idea moved into the textbooks of computer science and, as the spectacles of 'state space,' still lights up new puzzles today. The few rings stacked on a wooden peg in 1883 quietly remind us how very old the sources of our thinking-tools can be.

A Benares night; the tower still in motion (illustration, AI-generated)