ハノイの塔のゲームでは、1回動かすのに1秒かかると考えた時、塔の板が8枚に増えた場合、最小で済む移動回数は255回で3分15秒で完了させることができます。このサイトでも最大8枚まで遊べます。
ハノイの塔は、板の枚数をn枚としたとき、最少移動回数は2n-1となるゲームです。フィボナッチ数列の研究でも有名なフランスの数学者リュカが考えました。
Mn=2n-1
ハノイの塔の最少移動回数はメルセンヌ数とも呼ばれています。
メルセンヌ数が素数の時、メルセンヌ素数と呼ばれます。
ハノイの塔の板が20枚まで増えた時、完成までに12日以上かかり、25枚では1年以上、40枚では約3万4千年以上かかります。では、100枚だったら・・・？
計算方法
まず、板n枚の時の最少回数を2n-1で求め、その回数を31536000(=1年間の秒数)で割れば何年かかるか計算できます。
板が64枚として計算すると、完成には約5849億年以上かかり、いま私たちのいる宇宙の歴史（138億年）でさえ時間が足りません。
そして70枚で約3兆7436億年、90枚で約3925京（けい）4821兆1341億年と続き、
肝心の100枚の場合は、約401垓（がい）9693京（けい）6841兆3315億年かかることになります。
| ※背景がピンクの数字は、メルセンヌ素数です。 | ||
| 枚数(n) | 最少移動回数(Mn=2^n-1) | 完了までにかかる時間 |
|---|---|---|
| 2 | 3 | 3秒 |
| 3 | 7 | 7秒 |
| 4 | 15 | 15秒 |
| 5 | 31 | 31秒 |
| 6 | 63 | 1分3秒 |
| 7 | 127 | 2分7秒 |
| 8 | 255 | 3分15秒 |
| 9 | 511 | 6分31秒 |
| 10 | 1023 | 17分3秒 |
| 11 | 2047 | 34分7秒 |
| 12 | 4095 | 1時間8分15秒 |
| 13 | 8191 | 2時間16分31秒 |
| 14 | 16383 | 4時間33分3秒 |
| 15 | 32767 | 9時間6分7秒 |
| 16 | 65535 | 18時間12分15秒 |
| 17 | 131071 | 1日と12時間24分31秒 |
| 18 | 262143 | 3日と0時間49分3秒 |
| 19 | 524287 | 6日と1時間38分7秒 |
| 20 | 1048575 | 12日と3時間16分15秒 |
| 21 | 2097151 | 24日と6時間32分31秒 |
| 22 | 4194303 | 1ヶ月17日と13時間5分3秒 |
| 23 | 8388607 | 3ヶ月6日と2時間10分7秒 |
| 24 | 16777215 | 6ヶ月12日と4時間20分15秒 |
| 25 | 33554431 | 約1年 |
| 26 | 67108863 | 約2年 |
| 27 | 134217727 | 約4年 |
| 28 | 268435455 | 約8年 |
| 29 | 536870911 | 約17年 |
| 30 | 1073741823 | 約34年 |
| 31 | 2147483647 | 約68年 |
| 32 | 4294967295 | 約136年 |
| 33 | 8589934591 | 約272年 |
| 34 | 17179869183 | 約544年 |
| 35 | 34359738367 | 約1089年 |
| 36 | 68719476735 | 約2179年 |
| 37 | 137438953471 | 約4358年 |
| 38 | 274877906943 | 約8716年 |
| 39 | 549755813887 | 約17432年 |
| 40 | 1099511627775 | 約34865年 |
| 41 | 2199023255551 | 約69730年 |
| 42 | 4398046511103 | 約139461年 |
| 43 | 8796093022207 | 約278922年 |
| 44 | 17592186044415 | 約557844年 |
| 45 | 35184372088831 | 約1115689年 |
| 46 | 70368744177663 | 約2231378年 |
| 47 | 140737488355327 | 約4462756年 |
| 48 | 281474976710655 | 約8925512年 |
| 49 | 562949953421311 | 約17851025年 |
| 50 | 1125899906842620 | 約35702051年 |
| 51 | 2251799813685250 | 約71404103年 |
| 52 | 4503599627370490 | 約142808207年 |
| 53 | 9007199254740990 | 約285616414年 |
| 54 | 18014398509482000 | 約571232829年 |
| 55 | 36028797018964000 | 約1142465658年 |
| 56 | 72057594037927900 | 約2284931317年 |
| 57 | 144115188075856000 | 約4569862635年 |
| 58 | 288230376151712000 | 約9139725271年 |
| 59 | 576460752303423000 | 約18279450542年 |
| 60 | 1152921504606850000 | 約36558901084年 |
| 61 | 2305843009213693951 | 約73117802169年 |
| 62 | 4611686018427390000 | 約146235604338年 |
| 63 | 9223372036854780000 | 約292471208677年 |
| 64 | 18446744073709600000 | 約584942417355年 |
| 65 | 36893488147419100000 | 約1169884834710年 |
| 66 | 73786976294838200000 | 約2339769669420年 |
| 67 | 147573952589676000000 | 約4679539338840年 |
| 68 | 295147905179353000000 | 約9359078677681年 |
| 69 | 590295810358706000000 | 約18718157355362年 |
| 70 | 1180591620717410000000 | 約37436314710724年 |
| 71 | 2361183241434820000000 | 約74872629421449年 |
| 72 | 4722366482869650000000 | 約149745258842898年 |
| 73 | 9444732965739290000000 | 約299490517685797年 |
| 74 | 18889465931478600000000 | 約598981035371594年 |
| 75 | 37778931862957200000000 | 約1197962070743190年 |
| 76 | 75557863725914300000000 | 約2395924141486370年 |
| 77 | 151115727451829000000000 | 約4791848282972750年 |
| 78 | 302231454903657000000000 | 約9583696565945500年 |
| 79 | 604462909807315000000000 | 約19167393131891000年 |
| 80 | 1208925819614630000000000 | 約38334786263782000年 |
| 81 | 2417851639229260000000000 | 約76669572527564000年 |
| 82 | 4835703278458520000000000 | 約153339145055128000年 |
| 83 | 9671406556917030000000000 | 約306678290110256000年 |
| 84 | 19342813113834100000000000 | 約613356580220512000年 |
| 85 | 38685626227668100000000000 | 約1226713160441020000年 |
| 86 | 77371252455336300000000000 | 約2453426320882050000年 |
| 87 | 154742504910673000000000000 | 約4906852641764100000年 |
| 88 | 309485009821345000000000000 | 約9813705283528190000年 |
| 89 | 618970019642690137449562111 | 約19627410567056400000年 |
| 90 | 1237940039285380000000000000 | 約39254821134112800000年 |
| 91 | 2475880078570760000000000000 | 約78509642268225500000年 |
| 92 | 4951760157141520000000000000 | 約157019284536451000000年 |
| 93 | 9903520314283040000000000000 | 約314038569072902000000年 |
| 94 | 19807040628566100000000000000 | 約628077138145804000000年 |
| 95 | 39614081257132200000000000000 | 約1256154276291610000000年 |
| 96 | 79228162514264300000000000000 | 約2512308552583220000000年 |
| 97 | 158456325028529000000000000000 | 約5024617105166430000000年 |
| 98 | 316912650057057000000000000000 | 約10049234210332900000000年 |
| 99 | 633825300114115000000000000000 | 約20098468420665700000000年 |
| 100 | 1267650600228230000000000000000 | 約40196936841331500000000年 |
さぁ、ハノイの塔。あなたは何枚まで挑戦してみたいですか？笑