# Algorithm for Tower of Hanoi

Tower of Hanoi was a mathematical puzzle invented by Lucas 1883, France. There are many legends and myths about it as well. One myth I know is that the world will end if 64 tower disks’ Tower of Hanoi is completed. Lets see why the myth could be true.

**Algorithm**

A1: If the number of disks is even, move the first disk to tower 2. If the number of disks is odd, move the first disk to tower 3.

A2: All other numbers of disks have this same pattern: first move all disks except the base disk to tower 2, then move the base disk to tower 3.

A3: If the number of disks is even, move the smallest disks to tower 1. If the number of disks is odd, move the smallest disk to tower 3, and continue.

**The patterns**

A4: To find the minimum number of times to move the disk, follow this pattern

1 disk = move 1 time

2 disks = (1 x 2) + 1 = 3 times

3 disks = (3 x 2) + 1 = 7 times

4 disks = (7 x 2) + 1 = 15 times

5 disks = (9 x 2) + 1 = 31 times

…And so on. So the pattern is ‘{(the previous number of times) x 2} + 1’.

A5: There are other things you can do with this pattern…like calculating how many times you need to move 64 disks. Let’s start off with 1 disk and find the pattern…

**1 disk** (1 time) + 1 = (0+1) x 2 = 2 = 21

**2 disks **(3 times) + 1 = (1+1) x 2 = 4 = 22

**3 disks** (7 times) + 1 = (3+1) x 2 = 8 = 23

**4 disks** (15 times) + 1 = (7+1) x 2 =16 = 24

So we come up with a formula…

‘n disk: (#min. moves) + 1 = {(previous #min. moves)+1} x 2

Notice that the number required to move n number of disk is 2^n-1

Therefore, the minimum number required to move 64 disks is 2^64–1.