*有理数の樹

COLOR(#000066){最近仲間内での勉強会で話したネタです。次の樹の枝をどんどん枝分かれさせながら無限に書き続けていくと，すべての正の有理数がちょうど1回ずつ，既約分数の形で現れるのです。}

#ref(yuurisuunoki.png)

COLOR(#000066){これを横にたどって一番上の行，その次の行，と並べて一行にすると，すべての正の有理数がちょうど1回ずつ既約分数の形で現れる数列ができます。その数列は，ある項の分母が次の項の分子と等しい，という性質を持っています。この数列の分子をf(n)，n=0,1,2,3,…，とおくと，f(n)は簡単な漸化式で表せます。見た目がとっつきやすくて，有理数，数列，漸化式，ユークリッドの互除法と，いろいろなところに結び付けられそうです。}

COLOR(#006789){なるほどなるほど。このツリーで，ある既約分数，たとえば 5/9 を探すにはどうしたらよいかというアルゴリズムの問題は，とても簡単なのですね。左に下がるときには分子が変化せず，右に下がるときには分母が変化しないから。あまりエレガントではありませんが。繰り返しのアルゴリズムを使わないで一発で位置を計算するにはどうしたらいいのかな。}

COLOR(#fe891c){分母と分子の和が次への鍵で、左下へは分母に、右下には分子に摩り替わるわけかあ。ふむふむ。「ちょうど一回ずつ」というところが面白そう。本当かなあ。しかも既約分数で？うーん。うーん。ちょっくら遊んでみようっと。}

COLOR(#006789){ところで無理数はこのグラフの「どこ」に現れるのでしょうか？グラフの端点（ノード）には有理数しかこないのだから，どっかの「すきま」とか？言葉を変えて言うと，カントールの対角線論法みたいにして，このグラフから無理数を構成できないかと・・・}
トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS