How Many Moves to Move 64 Disks?

Fewest moves, disk by disk

Use the tower above (↺ starts the same tower again).

• a.Solve 1 disk, then 2 disks. What are the fewest moves for each?
• b.Solve 3 disks. The board tells you when nobody could have done it in fewer: keep trying until the ✓ appears.
• c.Now 4 disks. Before you start, look at your table and predict the fewest moves. Then check.

Watch the fewest moves

Now let the page make the fewest moves, one at a time. A strip records which disk moved each time, and the counts say how often each disk has moved.

• a.Which disk moves on every second move?
• b.With 4 disks, where are the other three disks when the biggest disk moves? Is it the same with 5 and 6 disks?
• c.When the tower is done, look at the counts. How many times did the biggest disk move? The next biggest? The smallest?

A rule your hands can follow

Here is a rule that needs no thinking at all. Picture the three pegs in a circle, so that after C comes A again.

1. Move the smallest disk one peg round the circle, always the same way: A → B → C → A when the tower has an even number of disks, A → C → B → A when it has an odd number.
2. Make the only other move you can: between the two pegs the smallest disk is not on, move the smaller top disk onto the other peg.

Repeat 1 and 2 until the tower is on C. Step 2 never needs a choice: the smaller of the two top disks can only go one way.

Go back to the first tower and try the rule with 4 disks, then with 5. Did you reach 15 and 31?

Why double, and one more?

Look at the biggest disk. It can only move when nothing is on top of it and the peg it goes to is empty, since nothing can sit under it. So at the moment it moves, every other disk must be on the third peg: a tower of its own, one disk smaller.

So a tower of 4 takes 7 + 1 + 7 = 15 moves, and a tower of 5 takes 15 + 1 + 15 = 31. Every extra disk doubles the moves, and adds one. Nobody can do better: the tower above the biggest disk has to be moved off it and back on, whatever order you make the moves in.

Counting by disk

The counts from the second tower give the same totals another way: with 4 disks, 8 + 4 + 2 + 1 = 15; with 5 disks, 16 + 8 + 4 + 2 + 1 = 31. Add up doubling numbers from 1, and the total is always one less than the next doubling: 15 is one less than 16.

One less than a power of 2

So the fewest moves for n disks is 2 × 2 × … × 2 (n twos), minus 1, written 2ⁿ − 1:

You may have met 2⁶⁴ − 1 before, in Grade 8: it is the number of grains of rice on a whole chessboard, 1 grain on the first square, 2 on the next, then 4, doubling to the 64th. The tower’s moves and the chessboard’s grains are the same sum: 1 + 2 + 4 + … doubling 64 times.

In binary, from Grade 6, a number one less than a power of 2 is all ones: 15 is 1111, 31 is 11111. The fewest moves for 64 disks is 64 ones in a row.

With blocks: the doubling

The rule in a block program: start from 0 moves, and for each disk, double and add one. The program asks how many disks, so it can’t use a plain repeat with a fixed number. It counts the disks done instead, and uses repeat until all of them are done.

Now try bigger towers. Run it with 20, then 30, then 64.

In Python (from Grade 8): how long?

The same doubling in Python, and the shortcut 2ⁿ − 1 beside it. bin() writes a number in binary, after the letters 0b.

moves = 0for disks in range(1, 11):    moves = moves * 2 + 1    print(disks, 'disks:', moves, 'moves', 2 ** disks - 1, bin(moves))

1 disks: 1 moves 1 0b12 disks: 3 moves 3 0b113 disks: 7 moves 7 0b1114 disks: 15 moves 15 0b11115 disks: 31 moves 31 0b111116 disks: 63 moves 63 0b1111117 disks: 127 moves 127 0b11111118 disks: 255 moves 255 0b111111119 disks: 511 moves 511 0b11111111110 disks: 1023 moves 1023 0b1111111111

The doubling and the shortcut agree, and every answer is a row of ones in binary.

Now the priests’ question: at one move a second, how long? The function how_long turns seconds into minutes, hours, days or years, whichever reads best. A year is 365.25 days, counting the leap years.

def how_long(seconds):    minutes = seconds / 60    hours = minutes / 60    days = hours / 24    years = days / 365.25    if minutes < 60:        return str(round(minutes)) + ' minutes'    elif hours < 24:        return str(round(hours)) + ' hours'    elif days < 365:        return str(round(days)) + ' days'    else:        return str(round(years)) + ' years' for disks in [8, 10, 20, 30, 40, 50, 64]:    moves = 2 ** disks - 1    print(disks, 'disks:', moves, 'moves,', how_long(moves))

8 disks: 255 moves, 4 minutes10 disks: 1023 moves, 17 minutes20 disks: 1048575 moves, 12 days30 disks: 1073741823 moves, 34 years40 disks: 1099511627775 moves, 34841 years50 disks: 1125899906842623 moves, 35677615 years64 disks: 18446744073709551615 moves, 584542046091 years

Your program plays the tower

Counting is one thing; can a program play? This one follows the rule from Try it. The pegs are three lists of disks, bottom first: [[4, 3, 2, 1], [], []] is a tower of 4 on A. pegs[0].pop() takes the last item (the top disk) off a list and gives it back, so pegs[2].append(pegs[0].pop()) moves A’s top disk onto C; pegs[1][-1], the last item, is B’s top disk, left in place. (small + step) % 3 goes round the circle 0, 1, 2: the remainder turns 3 back into 0, so after C comes A.

After every move the program draws the tower as a list of rows of letters, one square each, and show_frames, from the page’s own pixels module, shows them as steps (colors gives each letter its color).

from pixels import show_frames def picture(pegs, n):    rows = []    for level in range(n, -1, -1):        row = '.'        for peg in pegs:            if level < len(peg):                d = peg[level]                row = row + '.' * (n - d) + str(d) * (2 * d + 1) + '.' * (n - d) + '.'            else:                row = row + '.' * n + '|' + '.' * n + '.'        rows.append(row)    rows.append('=' * len(rows[0]))    return rows n = 4pegs = [[4, 3, 2, 1], [], []]     # A, B and C, bottom disk firstframes = [picture(pegs, n)]if n % 2 == 0:    step = 1                      # the smallest disk goes A, B, C, A...else:    step = 2                      # A, C, B, A...small = 0                         # the peg the smallest disk is onwhile len(pegs[2]) < n:    # 1. the smallest disk, one peg round    to = (small + step) % 3    pegs[to].append(pegs[small].pop())    small = to    frames.append(picture(pegs, n))    if len(pegs[2]) == n:        break    # 2. the only other move, between the other two pegs    a = (small + 1) % 3    b = (small + 2) % 3    if len(pegs[b]) == 0 or (len(pegs[a]) > 0 and pegs[a][-1] < pegs[b][-1]):        pegs[b].append(pegs[a].pop())    else:        pegs[a].append(pegs[b].pop())    frames.append(picture(pegs, n)) print(len(frames) - 1, 'moves')print(pegs)colors = {'.': 'white', '|': 'gray', '=': 'dimgray',          '1': 'crimson', '2': 'orange', '3': 'seagreen', '4': 'teal'}show_frames(frames, colors)

15 moves[[], [], [4, 3, 2, 1]]

Picture

Press Play under the picture to watch your program’s 15 moves. In step 2, the if asks: is peg b empty, or is the top of a smaller? Then the disk goes from a to b; otherwise from b to a. Make it a tower of 5 (n = 5, [[5, 4, 3, 2, 1], [], []] and '5': 'royalblue' in colors): does it take 31 moves?

Every tower, counted

Now the same rule as a function, without pictures. solve(n) plays a tower of n disks and gives back a list of the disks it moved, in order. list(range(n, 0, -1)) makes the tower: n, n − 1, … down to 1. order.count(disk) counts how many times disk is in the list.

def solve(n):    pegs = [list(range(n, 0, -1)), [], []]    if n % 2 == 0:        step = 1    else:        step = 2    small = 0    order = []    while len(pegs[2]) < n:        to = (small + step) % 3        pegs[to].append(pegs[small].pop())        order.append(1)        small = to        if len(pegs[2]) == n:            break        a = (small + 1) % 3        b = (small + 2) % 3        if len(pegs[b]) == 0 or (len(pegs[a]) > 0 and pegs[a][-1] < pegs[b][-1]):            disk = pegs[a].pop()            pegs[b].append(disk)        else:            disk = pegs[b].pop()            pegs[a].append(disk)        order.append(disk)    return order for n in range(1, 11):    print(n, 'disks:', len(solve(n)), 'moves') order = solve(5)print(order)for disk in range(1, 6):    print('Disk', disk, 'moved', order.count(disk), 'times')

1 disks: 1 moves2 disks: 3 moves3 disks: 7 moves4 disks: 15 moves5 disks: 31 moves6 disks: 63 moves7 disks: 127 moves8 disks: 255 moves9 disks: 511 moves10 disks: 1023 moves[1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1]Disk 1 moved 16 timesDisk 2 moved 8 timesDisk 3 moved 4 timesDisk 4 moved 2 timesDisk 5 moved 1 times

The program never counts “double and add one”: it just plays, following two simple steps. Yet its numbers are exactly 2ⁿ − 1, and its list is the ruler pattern from the strip.

• 64 disks take 18,446,744,073,709,551,615 moves, more than 18 billion billion. At one move a second, that is about 585 billion years. The universe is about 13.8 billion years old, so the priests would need more than 40 times its age.
• Every extra disk doubles the work. 10 disks take about 17 minutes; 20 disks, 12 days; 30 disks, 34 years, a working life; 40 disks, about 35,000 years. Each 10 more disks multiply the time by 1,024.

Could a computer do it?

Your solve plays a tower far faster than any priest. How much faster? This program times it for towers of 12 to 18 disks with time.perf_counter(), a clock that counts seconds, then works out from the last tower how long this computer would need for 64 disks.

import time def solve(n):    pegs = [list(range(n, 0, -1)), [], []]    if n % 2 == 0:        step = 1    else:        step = 2    small = 0    order = []    while len(pegs[2]) < n:        to = (small + step) % 3        pegs[to].append(pegs[small].pop())        order.append(1)        small = to        if len(pegs[2]) == n:            break        a = (small + 1) % 3        b = (small + 2) % 3        if len(pegs[b]) == 0 or (len(pegs[a]) > 0 and pegs[a][-1] < pegs[b][-1]):            disk = pegs[a].pop()            pegs[b].append(disk)        else:            disk = pegs[b].pop()            pegs[a].append(disk)        order.append(disk)    return order for n in range(12, 19):    start = time.perf_counter()    moves = len(solve(n))    seconds = time.perf_counter() - start    print(n, 'disks:', moves, 'moves in', round(seconds, 4), 'seconds') per_move = seconds / movesyears = per_move * (2 ** 64 - 1) / (60 * 60 * 24 * 365.25)print('64 disks on this computer: about', round(years), 'years')

Your times depend on your computer, so they aren’t printed here. These are ours:

The times changed from run to run by a quarter or so, and a phone may well be slower still. But on any computer, each extra disk about doubles the time: look down your own column of seconds. A computer makes millions of moves a second where the priests make one, and still can’t finish.

That is the lesson programmers take from the tower. When each extra piece of a problem doubles the work, a faster computer hardly helps: one twice as fast manages just one more disk in the same time. It is why a long password is so hard to guess (each extra bit of a key doubles the guesses, Grade 9), and why some problems will never be solved by trying every possibility.

Four pegs. Add a fourth peg, and the tower gets much easier. One good way: move some of the top disks, say k of them, out of the way using all four pegs; move the other n − k to the end with the three pegs left (2ⁿ⁻ᵏ − 1 moves, as before); then bring the k back on top, using all four pegs again. This program tries every k for each tower and keeps the best, building a list of the fewest moves for 1, 2, 3… disks:

fewest = [0]                      # 0 disks: 0 movesfor n in range(1, 65):    best = 0    for k in range(n):        moves = 2 * fewest[k] + 2 ** (n - k) - 1        if best == 0 or moves < best:            best = moves    fewest.append(best) print(fewest[1:11])print('64 disks:', fewest[64], 'moves')

[1, 3, 5, 9, 13, 17, 25, 33, 41, 49]64 disks: 18433 moves

With four needles, the priests would finish in 18,433 moves: about 5 hours. J. S. Frame and B. M. Stewart described this method in 1941, but proving that nothing does better took until 2014, when the mathematician Thierry Bousch did it.

An open question. For five or more pegs, the same kind of method is still the best anyone knows, and nobody has proved that it is the best there is.

★ The smallest disk (blocks)

The smallest disk moves on every other move. Finish the program so that it says how many times the smallest disk moves in a tower of the number of disks typed. Then press Test.

★★ Which disk moves? (Python, from Grade 8)

Write which_disk(m): the disk that moves on move number m of the fewest moves (for a tower big enough to have a move m). Your function must be quick even for m in the trillions, so it can’t play the tower.

def which_disk(m):    # the disk that moves on move m    return 1 print(which_disk(8))

★★★ Where are the priests? (Python, from Grade 8)

Write peg_of(n, k, m): in a tower of n disks moved from A to C in the fewest moves, which peg ('A', 'B' or 'C') is disk k on after m moves? Some tests are the legend’s tower of 64 disks after billions of moves, far too many to play.

def peg_of(n, k, m):    # the peg disk k is on after m moves of a tower of n disks    return 'A' print(peg_of(3, 1, 1))

• Grade 6, Zeros and Ones: every extra bit doubles the patterns, the same doubling as every extra disk.
• Grade 7, Variables and Choices: a variable that grows in a loop, as moves did.
• Grade 8, From Blocks to Python: Python’s whole numbers as big as you like, and the rice on the chessboard.
• Grade 9, Secrets and Security: why each extra bit of a key doubles the work of guessing it.
• Grade 11, Recursion: the tower solved by a function that calls itself, in seven lines, and the proof that 2ⁿ − 1 is the fewest.
• How does the mind-reading card trick work? More doubling, hidden in five cards of numbers.
• How do you always win at Nim? Another puzzle whose secret is written in binary.