１９世紀の数学者リュカの考案したゲームに「ハノイの塔」があります．ハノイの塔とは３本の柱Ａ，Ｂ，Ｃがあり，柱Ａにある何枚かの円盤を１枚ずつ柱Ｂを中継点にして柱Ｃに移動させるものです．ただし，どの柱でも上の円盤の方が小さくなければなりません．
（問）６４枚の円盤があるとき，移し替えが完了するには何回移動しなければならないのか？
円盤が３枚であるとします．Ａにある３枚をＢに移すにはＣを中継点にしてＢに移動させる．このためには上の２枚をＣに移し，３枚目をＢにもってきた後，Ｃの２枚をＢに移動させる．次に円盤が４枚であるとします．上の三枚がくっついているとして，この３枚をＢに移し，一番下の円盤をＣにもってきて，Ｂの３枚をＣに移せばよい．
このような再帰的な方法を用いれば円盤が何枚あってもＡからＣに移動させることができるのですが，ｎ枚の円盤を移動させるのに必要な最小回数をａnと書くことにすれば，漸化式
ａn＝２ａn-1＋１
で表せることがわかります．いま述べたｎ−１枚がくっついているとして・・・という考え方を小学５年生の息子に説明したところ，彼にも意味が理解できた様子でありました．
ａnの具体的な値は
ａn＋１＝２（ａn-1＋１）
ａn-1＋１＝２（ａn-2＋１）
・・・・・・・・・・・・・
ａ2＋１＝２（ａ1＋１）
より，容易に
ａn＝２^n−１
で与えられることがわかりますが，こうして円盤が３枚のとき→４枚のとき→ｎ枚のときに一般化することができます．
（答）６４枚の円盤があるとき，２^64−１回の移動をしなければならない．１秒に１回移動をさせるにしても完了までには５８２０億年かかることになる．
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
形は似ていますが，柱が３本のとき→４本のとき→ｎ本のときに一般化するのはもっと難しい問題になります．４本のときのハノイの塔について
一松信「整数と遊ぼう」日本評論社
の面白い記事がでていたので紹介します．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【１】柱を４本にしたときの手間
あるとき，一松先生が熱心な中学生のグループから４本のときのハノイの塔について質問を受けたそうです．彼等が実験したところによると，その手間は
ｎ １ ２ ３ ４ ５ ６ ７ ８ ９ 10
ｂ １ ３ ５ ９ 13 17 25 33 41 49
もちろん２^n−１に比べると桁違いに少ない回数です．
差分をとってみると
２ ２ ４ ４ ４ ８ ８ ８ ８・・・
となって，その先は
１６ １６ １６ １６ １６ ３２ ３２ ３２ ３２ ３２ ３２・・・（２^nがｎ＋１個続く）
このことから，４本のときのハノイの塔でもやはり枚数ｎの増加とともなって指数関数的に手間が増加することがわかります．ただしその増加が３本のときのハノイの塔（２^n−１）と比べ，桁違いに遅いというわけです．柱をいくら増やしても板の枚数の増加とともに指数関数的に増加します．
そして，記事の最後に一松先生は「ハノイの塔の柱を１本増やす」という発展問題を考えた中学生に改めて敬意を表していますが，確かにこうした発想をつまらないものとして芽を摘むのは最悪の教育でしょう．私も大学院生のとき，微量元素の分析に現れる曲線は何かと考えて，当時の教授から「つまらないことを考えるな」とどやしつけられたことがあり，そのことを思い出しました．その曲線とはいまにして思えばフォークト関数です．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【２】リュカとフィボナッチ数列
初項１，第２項１から始まり，隣り合う２項の和が次の項となる数列
１，１，２，３，５，８，・・・
をフィボナッチ数列とよびます．その一般項Ｆn は
Ｆn＝Ｆn-1＋Ｆn-2
です．この数列にフィボナッチ（１３世紀のイタリアの数学者でピサのレオナルドとしても知られる）の名を冠したのはフランスの数学者リュカで，ハノイの塔の名で知られる２進法のパズルも１８８３年にリュカによって考案されたものです．
初項２，第２項１のフィボナッチ数列
２，１，３，４，７，１１，１８，・・・
は彼にちなんでリュカ数列と呼ばれています（１８７７年）．
Ｌn＝Ｌn-1＋Ｌn-2
リュカはフィボナッチ数列，リュカ数列を用いてメルセンヌ数（２^n−１）が素数であるかどうかを判定し，（２^127−１）が素数であることを示しています（１８７６年）．この数は１２番目のメルセンヌ素数で，１９５２年の１３番目（２^521−１）からはコンピュータによる発見ですから，コンピュータを使わずに見つけられた最大のメルセンヌ素数になっていて，わかっている最大の素数として最長不倒記録を保ち続けました．
フィボナッチ数列やリュカ数列の一般項は，３項漸化式：
Ｆn＝Ｆn-1＋Ｆn-2
Ｌn＝Ｌn-1＋Ｌn-2
の特性方程式
ｘ^2−ｘ−１＝０
の２つの解より，連続する２項の比は黄金比
φ＝（１＋√５）／２＝１．６１８０３４・・・
に次第に近づくことになります．
黄金長方形から正方形を取り除くと一回り小さな黄金長方形が現れてきます．このことを繰り返し行えば対数らせんが現れますが，この曲線は自然界ではオーム貝などの形にみられ，自己相似的な成長過程を表す理想的な曲線とされています．サイクロイドの伸開線はそれと合同なサイクロイドですが，対数らせんの伸開線もそれと合同な対数らせんになります．
今度は逆に１辺の長さがフィボナッチ数列の正方形をらせん状に加えていきます．最初の２つの正方形は１辺の長さが１で，そこに１辺の長さが２の正方形，引き続いて１辺の長さが３，５，８，１３，２１，・・・．すると，優美な対数らせんが現れてきますが，このらせんはほぼ黄金比で外に広がることになります．
さらに，１つの項の和がその前の３つの項の和になっている
Ｔn＝Ｔn-1＋Ｔn-2＋Ｔn-3
で定義される数列
１，１，１，３，５，９，１７，・・・
は，フィボナッチ数列の拡張とみなせるので，フィボナッチ（Fibonacci）をもじってトリボナッチ（Tribonacci）数列と呼ばれます．
トリボナッチ数列でも連続する２項の比はある決まった値
１／３｛3√（１９＋３√３３）＋3√（１９−３√３３）＋１｝＝１．８３９・・・
に収束します．これは
ｘ^3−ｘ^2−ｘ−１＝０
の実根です．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【３】リュカとペラン数列
フィボナッチ数列では正方形をらせん状に並べましたが，次に正三角形をらせん状に並べてみましょう．最初の３つの正三角形は１辺の長さを１，次の２つは１辺の長さが２で，そのあとは３，４，５，７，９，１２，１６，２１，・・・．このようにしてもおおよそ対数らせんを描きます．
数列
１，１，１，２，２，３，４，５，７，９，１２，１６，２１，・・・
は直前の１項を除いたその前の２項を加えたものです．パドヴァンの数列と呼ぶことにしますが，漸化式は
Ｐn＝Ｐn-2＋Ｐn-3 （Ｐ0＝Ｐ1＝Ｐ2＝１）
で表されます．
その特性方程式
ｘ^3−ｘ−１＝０
の唯一の実数解より，パドヴァン数列の連続する２項の比は
ｐ＝１／３｛3√（２７／２−３√６９／２）＋3√（１／２＋√６９／１８）｝＝１．３２４７１８・・・
に次第に近づくことになります．ｐがφよりも小さいことより，パドヴァン数列はフィボナッチ数列に較べてゆっくりと増加することになります．
ｐ^5−ｐ^3−ｐ^2＝０
ｐ^4−ｐ^2−ｐ^1＝０
より
ｐ^5−ｐ^4−ｐ^3−ｐ^1＝ｐ^5−ｐ^4−１
ですから，３次方程式ｐ^3−ｐ−１＝０の解はこの５次方程式も満たすことがわかります．あるいは，因数分解
ｐ^5−ｐ^4−１＝（ｐ^3−ｐ−１）（ｐ^2−ｐ＋１）
でもよいのですが，このことから
Ｐn＝Ｐn-1＋Ｐn-5
の関係が成り立つこともわかります．
リュカはパドヴァン数列と同じ生成規則に従い，最初の項の値が異なるものを考案しました（１８７６年）．
Ａn＝Ａn-2＋Ａn-3 （Ａ0＝３，Ａ1＝０，Ａ2＝２）
３，０，２，３，２，５，５，７，１０，１２，１７，２２，２９，・・・
この数列は現在ではペラン数列と呼ばれるものです．この数列の項比もｐに近づきますが，さらに深遠な性質「ｎが素数のときＡnはｎで割り切れる」をもっています．しかし，逆命題「Ａnがｎで割り切れるときｎは素数である」は必ずしも成り立たないことが知られています．ただし，その最小の反例は数万の大きさなので，コンピュータでも使わなければ反証できません．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【４】リュカの問題
１^2＋２^2＋３^2＋・・・＋２４^2＝２４（２４＋１）（２・２４＋１）／６＝７０^2
級数の公式：Σｋ^2＝ｎ（ｎ＋１）（２ｎ＋１）／６をご存じの方も多いでしょうが，１からｎまでの平方の和が平方数となるのはｎが１か２４の場合しかありません．
２５平方の等式ともいうべきこの等式はリュカの問題（１８７３年）として知られています．ｙ^2＝ｘ（ｘ＋１）（２ｘ＋１）／６の唯一自明でない整数解は（２４，７０）で，それ以外の自明な解がないことは楕円関数やペル方程式を使って証明されています．
この等式は辺の長さが相続く整数列１，２，・・・，２４の正方形を１辺の長さ７０の正方形の中に詰め込める可能性があることを示唆しています．それでは，実際に，７０×７０の正方形を辺が１から２４の相続く正方形によって埋めつくすことができるでしょうか．この問題の答えは否定的（不可能）です．１辺の長さ７の正方形を除くすべての正方形は詰め込めるのですが・・・．
それならば，無駄な空間の割合を最小にして，辺の長さが１，２，・・・，ｎの正方形を全て詰め込むことができる最小の正方形の辺の長さはいくつでしょうか．また，相続く整数辺の正方形を使って長方形を充填できるでしょうか．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝