完成すると世界が滅びるパズル？「ハノイの塔」の考案者エドゥアール・リュカの偉業（現代ビジネス） - Yahoo!ニュース - Yahoo!ニュース

手作業で発見された最大の素数

1842年の今日(4月4日)数学パズルの「ハノイの塔」を考案したフランスの数学者エドゥアール・リュカ(Édouard Lucas、1842-1891)が誕生しました。　もともとリュカは天文学を学んでおり、パリ天文台に務めた後に数学者として活躍しました。彼は整数論の中でも素数に着目し、あるメルセンヌ数が素数かどうかを判定する「リュカ・テスト」を考案しました。 　メルセンヌ数とは、「2のn乗から1を引いて表される整数」のことで、3(=2×2-1)、7(=2×2×2-1)、15(=2×2×2×2-1)……などが該当します。 　彼は「リュカ・テスト」を利用し、 　2の127乗マイナス1(=170141183460469231731687303715884105727) 　という39桁にも及ぶ天文学的な大きさのメルセンヌ数を分析しました。コンピュータのない時代、彼は約19年の歳月をかけ1876年に手作業でこのメルセンヌ数が素数であることを証明したのです。これは計算機を使わずに発見された最大の素数であり、1952年に記録が更新されるまで76年にわたって、人類が発見した最も大きな素数でした。 　リュカ・テスト(のちに改良されたリュカ–レーマー・テスト)では、メルセンヌ数 M=2のp乗－1(ただしpは奇素数)が素数となるための必要十分条件は、S[0] = 4, S[n] = S[n－1]^2 － 2 (n ≧ 1) と定義したときに S[p－2] が Mで割り切れること、となります。

完成すると世界が滅びるパズル

　リュカはまた「ハノイの塔」というパズルの考案者としても知られています。大きさがそれぞれ異なる円盤と3本の杭からなるパズルで、ある円盤の上にそれより大きな円盤を乗せてはならないというルールのもと、すべての円盤を別の杭に移し切るのが目標です。 　円盤を移しきるまでに必要な最短手数は、円盤の枚数をnとすると「2のn乗-1」回と表すことができます。つまり、3枚の円盤を使う場合は7回(=2×2×2-1)、4枚の円盤を使う場合は15回(=2×2×2×2-1)が最短手数となります。 　リュカが考案したオリジナルバージョンは64枚の円盤を使うもので、最短手数は2の64乗マイナス1=18446744073709551615回。1秒に1枚動かすとすると約6000億年かかる計算になり、確かに完成するまでに世界の1つや2つは終わってしまいそうです。

ブルーバックス編集部（科学シリーズ）

Let's block ads! (Why?)

からの記事と詳細 ( 完成すると世界が滅びるパズル？「ハノイの塔」の考案者エドゥアール・リュカの偉業（現代ビジネス） - Yahoo!ニュース - Yahoo!ニュース )
https://ift.tt/3sO3FmF