日本語

Let's play a game of the Tower of Hanoi.

Game Rules ↓

  1. Move the disks by clicking and dragging them one at a time.
  2. Larger disks cannot be placed on top of smaller disks.
  3. The game is won by moving all of the disks to the rod on the right and stacking them in the same order as the starting rod.

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.

Calculating the shortest amount of time needed to complete a Tower of Hanoi with 100 disks

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.

Formula
 (2n-1)÷31,536,000 = time (in years) needed to complete a Tower of Hanoi with n disks

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.



Table depicting the number of disks in a Tower of Hanoi and the time to completion

*Numbers with a pink background are Mersenne Primes.
# of disks (n)Minimum number of moves (Mn=2^n-1)Time to completion
233 seconds
377 seconds
41515 seconds
53131 seconds
6631 minute, 3 seconds
71272 minutes, 7 seconds
82553 minutes, 15 seconds
95116 minutes, 31 seconds
101,02317 minutes, 3 seconds
112,04734 minutes, 7 seconds
124,0951 hour, 8 minutes, 15 seconds
138,1912 hours, 16 minutes, 31 seconds
1416,3834 hours, 33 minutes, 3 seconds
1532,7679 hours, 6 minutes, 7 seconds
1665,53518 hours, 12 minutes, 15 seconds
17131,0711 day, 12 hours, 24 minutes, 31 seconds
18262,1433 days, 49 minutes, 3 seconds
19524,2876 days, 1 hour, 38 minutes, 7 seconds
201,048,57512 days, 3 hours, 16 minutes, 15 seconds
212,097,15124 days, 6 hours, 32 minutes, 31 seconds
224,194,3031 month, 17 days, 13 hours, 5 minutes, 3 seconds
238,388,6073 months, 6 days, 2 hours, 10 minutes, 7 seconds
2416,777,2156 months, 12 days, 4 hours, 20 minutes, 15 seconds
2533,554,431Approx. 1 year
2667,108,863Approx. 2 years
27134,217,727Approx. 4 years
28268,435,455Approx. 8 years
29536,870,911Approx. 17 years
301,073,741,823Approx. 34 years
312,147,483,647Approx. 68 years
324,294,967,295Approx. 136 years
338,589,934,591Approx. 272 years
3417,179,869,183Approx. 544 years
3534,359,738,367Approx. 1,089 years
3668,719,476,735Approx. 2,179 years
37137,438,953,471Approx. 4,358 years
38274,877,906,943Approx. 8,716 years
39549,755,813,887Approx. 17,432 years
401,099,511,627,775Approx. 34,865 years
412,199,023,255,551Approx. 69,730 years
424,398,046,511,103Approx. 139,461 years
438,796,093,022,207Approx. 278,922 years
4417,592,186,044,415Approx. 557,844 years
4535,184,372,088,831Approx. 1,115,689 years
4670,368,744,177,663Approx. 2,231,378 years
47140,737,488,355,327Approx. 4,462,756 years
48281,474,976,710,655Approx. 8,925,512 years
49562,949,953,421,311Approx. 17,851,025 years
501,125,899,906,842,620Approx. 35,702,051 years
512,251,799,813,685,250Approx. 71,404,103 years
524,503,599,627,370,490Approx. 142,808,207 years
539,007,199,254,740,990Approx. 285,616,414 years
5418,014,398,509,482,000Approx. 571,232,829 years
5536,028,797,018,964,000Approx. 1,142,465,658 years
5672,057,594,037,927,900Approx. 2,284,931,317 years
57144,115,188,075,856,000Approx. 4,569,862,635 years
58288,230,376,151,712,000Approx. 9,139,725,271 years
59576,460,752,303,423,000Approx. 18,279,450,542 years
601,152,921,504,606,850,000Approx. 36,558,901,084 years
612,305,843,009,213,693,951Approx. 73,117,802,169 years
624,611,686,018,427,390,000Approx. 146,235,604,338 years
639,223,372,036,854,780,000Approx. 292,471,208,677 years
6418,446,744,073,709,600,000Approx. 584,942,417,355 years
6536,893,488,147,419,100,000Approx. 1,169,884,834,710 years
6673,786,976,294,838,200,000Approx. 2,339,769,669,420 years
67147,573,952,589,676,000,000Approx. 4,679,539,338,840 years
68295,147,905,179,353,000,000Approx. 9,359,078,677,681 years
69590,295,810,358,706,000,000Approx. 18,718,157,355,362 years
701,180,591,620,717,410,000,000Approx. 37,436,314,710,724 years
712,361,183,241,434,820,000,000Approx. 74,872,629,421,449 years
724,722,366,482,869,650,000,000Approx. 149,745,258,842,898 years
739,444,732,965,739,290,000,000Approx. 299,490,517,685,797 years
7418,889,465,931,478,600,000,000Approx. 598,981,035,371,594 years
7537,778,931,862,957,200,000,000Approx. 1,197,962,070,743,190 years
7675,557,863,725,914,300,000,000Approx. 2,395,924,141,486,370 years
77151,115,727,451,829,000,000,000Approx. 4,791,848,282,972,750 years
78302,231,454,903,657,000,000,000Approx. 9,583,696,565,945,500 years
79604,462,909,807,315,000,000,000Approx. 19,167,393,131,891,000 years
801,208,925,819,614,630,000,000,000Approx. 38,334,786,263,782,000 years
812,417,851,639,229,260,000,000,000Approx. 76,669,572,527,564,000 years
824,835,703,278,458,520,000,000,000Approx. 153,339,145,055,128,000 years
839,671,406,556,917,030,000,000,000Approx. 306,678,290,110,256,000 years
8419,342,813,113,834,100,000,000,000Approx. 613,356,580,220,512,000 years
8538,685,626,227,668,100,000,000,000Approx. 1,226,713,160,441,020,000 years
8677,371,252,455,336,300,000,000,000Approx. 2,453,426,320,882,050,000 years
87154,742,504,910,673,000,000,000,000Approx. 4,906,852,641,764,100,000 years
88309,485,009,821,345,000,000,000,000Approx. 9,813,705,283,528,190,000 years
89618,970,019,642,690,137,449,562,111Approx. 19,627,410,567,056,400,000 years
901,237,940,039,285,380,000,000,000,000Approx. 39,254,821,134,112,800,000 years
912,475,880,078,570,760,000,000,000,000Approx. 78,509,642,268,225,500,000 years
924,951,760,157,141,520,000,000,000,000Approx. 157,019,284,536,451,000,000 years
939,903,520,314,283,040,000,000,000,000Approx. 314,038,569,072,902,000,000 years
9419,807,040,628,566,100,000,000,000,000Approx. 628,077,138,145,804,000,000 years
9539,614,081,257,132,200,000,000,000,000Approx. 1,256,154,276,291,610,000,000 years
9679,228,162,514,264,300,000,000,000,000Approx. 2,512,308,552,583,220,000,000 years
97158,456,325,028,529,000,000,000,000,000Approx. 5,024,617,105,166,430,000,000 years
98316,912,650,057,057,000,000,000,000,000Approx. 10,049,234,210,332,900,000,000 years
99633,825,300,114,115,000,000,000,000,000Approx. 20,098,468,420,665,700,000,000 years
1001,267,650,600,228,230,000,000,000,000,000Approx. 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?


Error

403 Forbidden アクセス権がありません

Date: 2017-11-22T19:56:26+09:00

your IP: 202.254.234.15