Game Rules ↓
If you consider it takes 1 second to move a single disk while playing the Tower of Hanoi, and there are a total of 8 disks, then the minimum number of moves needed to complete the game is 255, and it will take 3 minutes and 15 seconds. This site enables you to play a game using up to 8 disks.
When you play a game of the Tower of Hanoi with n number of disks, the minimum number of moves needed to complete the game is denoted by 2n-1 and was devised by the French mathematician, Édouard Lucas, who was famous for his study of the Fibonacci sequence.
Mn=2n-1
The minimum number of moves to complete a Tower of Hanoi is known as a Mersenne Number.
When a Mersenne Number is also a prime number, it is referred to as a Mersenne Prime.
A Tower of Hanoi consisting of 20 disks will take 12 days to complete, while 25 disks will take more than 1 year, and 40 disks will take approximately 34,000 years. How about 100 disks?
Calculation method
First, you use the formula 2n-1 to find the minimum number of moves needed for n disks. Then, divide that number by 31,536,000 (= # of seconds in 1 year) to calculate the number of years required.
Calculating the time needed for 64 disks, it will take more than 584.9 billion years, which is longer than the history of our known universe (approximately 13.8 billion years).
The previously mentioned tower with 100 disks would take approximately 40 sextillion 196 quintillion 936 quadrillion 841 trillion 331 billion and 500 million years to complete.
| *Numbers with a pink background are Mersenne Primes. | ||
| # of disks (n) | Minimum number of moves (Mn=2^n-1) | Time to completion |
|---|---|---|
| 2 | 3 | 3 seconds |
| 3 | 7 | 7 seconds |
| 4 | 15 | 15 seconds |
| 5 | 31 | 31 seconds |
| 6 | 63 | 1 minute, 3 seconds |
| 7 | 127 | 2 minutes, 7 seconds |
| 8 | 255 | 3 minutes, 15 seconds |
| 9 | 511 | 6 minutes, 31 seconds |
| 10 | 1,023 | 17 minutes, 3 seconds |
| 11 | 2,047 | 34 minutes, 7 seconds |
| 12 | 4,095 | 1 hour, 8 minutes, 15 seconds |
| 13 | 8,191 | 2 hours, 16 minutes, 31 seconds |
| 14 | 16,383 | 4 hours, 33 minutes, 3 seconds |
| 15 | 32,767 | 9 hours, 6 minutes, 7 seconds |
| 16 | 65,535 | 18 hours, 12 minutes, 15 seconds |
| 17 | 131,071 | 1 day, 12 hours, 24 minutes, 31 seconds |
| 18 | 262,143 | 3 days, 49 minutes, 3 seconds |
| 19 | 524,287 | 6 days, 1 hour, 38 minutes, 7 seconds |
| 20 | 1,048,575 | 12 days, 3 hours, 16 minutes, 15 seconds |
| 21 | 2,097,151 | 24 days, 6 hours, 32 minutes, 31 seconds |
| 22 | 4,194,303 | 1 month, 17 days, 13 hours, 5 minutes, 3 seconds |
| 23 | 8,388,607 | 3 months, 6 days, 2 hours, 10 minutes, 7 seconds |
| 24 | 16,777,215 | 6 months, 12 days, 4 hours, 20 minutes, 15 seconds |
| 25 | 33,554,431 | Approx. 1 year |
| 26 | 67,108,863 | Approx. 2 years |
| 27 | 134,217,727 | Approx. 4 years |
| 28 | 268,435,455 | Approx. 8 years |
| 29 | 536,870,911 | Approx. 17 years |
| 30 | 1,073,741,823 | Approx. 34 years |
| 31 | 2,147,483,647 | Approx. 68 years |
| 32 | 4,294,967,295 | Approx. 136 years |
| 33 | 8,589,934,591 | Approx. 272 years |
| 34 | 17,179,869,183 | Approx. 544 years |
| 35 | 34,359,738,367 | Approx. 1,089 years |
| 36 | 68,719,476,735 | Approx. 2,179 years |
| 37 | 137,438,953,471 | Approx. 4,358 years |
| 38 | 274,877,906,943 | Approx. 8,716 years |
| 39 | 549,755,813,887 | Approx. 17,432 years |
| 40 | 1,099,511,627,775 | Approx. 34,865 years |
| 41 | 2,199,023,255,551 | Approx. 69,730 years |
| 42 | 4,398,046,511,103 | Approx. 139,461 years |
| 43 | 8,796,093,022,207 | Approx. 278,922 years |
| 44 | 17,592,186,044,415 | Approx. 557,844 years |
| 45 | 35,184,372,088,831 | Approx. 1,115,689 years |
| 46 | 70,368,744,177,663 | Approx. 2,231,378 years |
| 47 | 140,737,488,355,327 | Approx. 4,462,756 years |
| 48 | 281,474,976,710,655 | Approx. 8,925,512 years |
| 49 | 562,949,953,421,311 | Approx. 17,851,025 years |
| 50 | 1,125,899,906,842,620 | Approx. 35,702,051 years |
| 51 | 2,251,799,813,685,250 | Approx. 71,404,103 years |
| 52 | 4,503,599,627,370,490 | Approx. 142,808,207 years |
| 53 | 9,007,199,254,740,990 | Approx. 285,616,414 years |
| 54 | 18,014,398,509,482,000 | Approx. 571,232,829 years |
| 55 | 36,028,797,018,964,000 | Approx. 1,142,465,658 years |
| 56 | 72,057,594,037,927,900 | Approx. 2,284,931,317 years |
| 57 | 144,115,188,075,856,000 | Approx. 4,569,862,635 years |
| 58 | 288,230,376,151,712,000 | Approx. 9,139,725,271 years |
| 59 | 576,460,752,303,423,000 | Approx. 18,279,450,542 years |
| 60 | 1,152,921,504,606,850,000 | Approx. 36,558,901,084 years |
| 61 | 2,305,843,009,213,693,951 | Approx. 73,117,802,169 years |
| 62 | 4,611,686,018,427,390,000 | Approx. 146,235,604,338 years |
| 63 | 9,223,372,036,854,780,000 | Approx. 292,471,208,677 years |
| 64 | 18,446,744,073,709,600,000 | Approx. 584,942,417,355 years |
| 65 | 36,893,488,147,419,100,000 | Approx. 1,169,884,834,710 years |
| 66 | 73,786,976,294,838,200,000 | Approx. 2,339,769,669,420 years |
| 67 | 147,573,952,589,676,000,000 | Approx. 4,679,539,338,840 years |
| 68 | 295,147,905,179,353,000,000 | Approx. 9,359,078,677,681 years |
| 69 | 590,295,810,358,706,000,000 | Approx. 18,718,157,355,362 years |
| 70 | 1,180,591,620,717,410,000,000 | Approx. 37,436,314,710,724 years |
| 71 | 2,361,183,241,434,820,000,000 | Approx. 74,872,629,421,449 years |
| 72 | 4,722,366,482,869,650,000,000 | Approx. 149,745,258,842,898 years |
| 73 | 9,444,732,965,739,290,000,000 | Approx. 299,490,517,685,797 years |
| 74 | 18,889,465,931,478,600,000,000 | Approx. 598,981,035,371,594 years |
| 75 | 37,778,931,862,957,200,000,000 | Approx. 1,197,962,070,743,190 years |
| 76 | 75,557,863,725,914,300,000,000 | Approx. 2,395,924,141,486,370 years |
| 77 | 151,115,727,451,829,000,000,000 | Approx. 4,791,848,282,972,750 years |
| 78 | 302,231,454,903,657,000,000,000 | Approx. 9,583,696,565,945,500 years |
| 79 | 604,462,909,807,315,000,000,000 | Approx. 19,167,393,131,891,000 years |
| 80 | 1,208,925,819,614,630,000,000,000 | Approx. 38,334,786,263,782,000 years |
| 81 | 2,417,851,639,229,260,000,000,000 | Approx. 76,669,572,527,564,000 years |
| 82 | 4,835,703,278,458,520,000,000,000 | Approx. 153,339,145,055,128,000 years |
| 83 | 9,671,406,556,917,030,000,000,000 | Approx. 306,678,290,110,256,000 years |
| 84 | 19,342,813,113,834,100,000,000,000 | Approx. 613,356,580,220,512,000 years |
| 85 | 38,685,626,227,668,100,000,000,000 | Approx. 1,226,713,160,441,020,000 years |
| 86 | 77,371,252,455,336,300,000,000,000 | Approx. 2,453,426,320,882,050,000 years |
| 87 | 154,742,504,910,673,000,000,000,000 | Approx. 4,906,852,641,764,100,000 years |
| 88 | 309,485,009,821,345,000,000,000,000 | Approx. 9,813,705,283,528,190,000 years |
| 89 | 618,970,019,642,690,137,449,562,111 | Approx. 19,627,410,567,056,400,000 years |
| 90 | 1,237,940,039,285,380,000,000,000,000 | Approx. 39,254,821,134,112,800,000 years |
| 91 | 2,475,880,078,570,760,000,000,000,000 | Approx. 78,509,642,268,225,500,000 years |
| 92 | 4,951,760,157,141,520,000,000,000,000 | Approx. 157,019,284,536,451,000,000 years |
| 93 | 9,903,520,314,283,040,000,000,000,000 | Approx. 314,038,569,072,902,000,000 years |
| 94 | 19,807,040,628,566,100,000,000,000,000 | Approx. 628,077,138,145,804,000,000 years |
| 95 | 39,614,081,257,132,200,000,000,000,000 | Approx. 1,256,154,276,291,610,000,000 years |
| 96 | 79,228,162,514,264,300,000,000,000,000 | Approx. 2,512,308,552,583,220,000,000 years |
| 97 | 158,456,325,028,529,000,000,000,000,000 | Approx. 5,024,617,105,166,430,000,000 years |
| 98 | 316,912,650,057,057,000,000,000,000,000 | Approx. 10,049,234,210,332,900,000,000 years |
| 99 | 633,825,300,114,115,000,000,000,000,000 | Approx. 20,098,468,420,665,700,000,000 years |
| 100 | 1,267,650,600,228,230,000,000,000,000,000 | Approx. 40,196,936,841,331,500,000,000 years |
And that is the Tower of Hanoi. Now, how many disks are you willing to try?