Tower of Hanoi with 64 Disks
The size of the legend. A perfect game takes eighteen quintillion moves — here is what that number means, and where the disks would be today.
Optimal solution
18,
2⁶⁴ − 1
- At one move a second
- 585 billion years
- At a billion a second
- 584 years
- Disk 64 moves once, on move
- 9,223,372,036,854,775,808
If the priests had started in 1883
The legend gives no start date, so take the year the puzzle was published. At one move a second since then, this is the game as it stands.
- Move number, on 10 September 2026
- 4,534,444,800
- Disk 1 has moved
- 2,267,222,400 times
- Largest disk to move so far
- Disk 33
- Share of the game done
- 0.0000000246%
Only the 8 smallest disks are drawn. The other 56 are beneath them, and disks 34 to 64 have never left tower A.
On this page
How big the number is
2⁶⁴ − 1 is 18,446,744,073,709,551,615: eighteen quintillion, four hundred and forty-six quadrillion and change. It is also a number every programmer has met without knowing it, because it is the largest value a 64-bit unsigned integer can hold — every one of its 64 bits set. The move count of the legend is, exactly, the biggest number most computers store in a single word, which is why counting it correctly is a trap in Java and JavaScript and needs care in C.
It is not prime. Numbers of the form 2ⁿ − 1 can only be prime when n is, and 64 is as far from prime as a number gets: 2⁶⁴ − 1 = 3 × 5 × 17 × 257 × 641 × 65,537 × 6,700,417.
How long it would take
| Speed | Time for every move |
|---|---|
| One move a secondThe pace every telling of the legend assumes. | 585 billion years |
| Three moves a secondAbout as fast as anyone moves disks by hand. | 195 billion years |
| A thousand moves a secondFaster than any mechanism could lift a disk. | 585 million years |
| A billion moves a secondA computer generating moves and doing nothing else. | 584 years |
At the legend's pace the game takes roughly 42 times the current age of the universe. Even a computer running flat out, producing a billion moves every second and printing none of them, would be at it for 584 years. There is no faster method to reach for: 2ⁿ − 1 is a proven minimum, so no algorithm and no amount of cleverness removes a single move.
What happens along the way
The largest disk moves exactly once, on move 9,223,372,036,854,775,808 — the halfway point. Everything before it is the 63-disk solution, building a tower on the middle peg; everything after is the 63-disk solution again, rebuilding it on top. The smallest disk does half of all the work: it moves 9,223,372,036,854,775,808 times, on every odd-numbered move.
Progress is invisible for a very long time. A whole human lifetime of moves, eighty years at one a second, is 2,524,608,000 moves — and the largest disk to have moved even once by then is disk 32. Disks 33 to 64 would not yet have been touched, and the tower would look, from across the room, exactly as it did at the start.
Why there is no move list here
Every other solution page lists every move. This one cannot, and not because of the page: written as tersely as possible, three characters and a line break a move — 1AC — the list would fill more than 73 exabytes. The pattern is the solution instead: the iterative rule gives the next move from the board alone, and the binary formula gives move number m for any m without playing the ones before it — which is how the board above knows where the disks are.
The legend
The sixty-four disks come from a story attached to the puzzle soon after Édouard Lucas published it in 1883: in a temple, priests move sixty-four golden disks between three diamond needles, one disk at a time, and when the last disk is placed the world will end. The arithmetic on this page is the reassuring part. The rest of the story, and how much of it was invented to sell a toy, is in the history of the Tower of Hanoi.
Frequently asked questions
How many moves does Tower of Hanoi with 64 disks take?
18,446,744,073,709,551,615 moves at the very least: 2⁶⁴ − 1. That is about 18.4 quintillion, and it is exactly the largest number an unsigned 64-bit integer can hold.
How long would it take a computer to solve 64-disk Tower of Hanoi?
A computer producing a billion moves a second, and doing nothing else, would need 584 years. At one move a second, the pace of the legend, it is 585 billion years — roughly 42 times the age of the universe.
Is 2⁶⁴ − 1 a prime number?
No. 2⁶⁴ − 1 = 3 × 5 × 17 × 257 × 641 × 65,537 × 6,700,417. A number of the form 2ⁿ − 1 can only be prime when n is prime, and 64 is not.
When is the 64-disk puzzle halfway done?
On move 9,223,372,036,854,775,808, which is the only time disk 64 moves. Before it, 63 disks are stacked on the middle tower; after it, the same 63 disks are moved again onto the largest disk. At one move a second, that halfway move comes after 292 billion years.