Calkin-Wilf tree
注:このページの内容はペンシルパズルとは無関係です。
Calkin-Wilf tree
作り方
1.一番上、1段目に1/1と書く。
2.次の段では、上に分数a/bがあるとき、左下にa/(a+b)、右下に(a+b)/bを書く。
3.繰り返す。
性質
上から分数を読んでいくと
1/1,
1/2, 2/1,
1/3, 3/2, 2/3, 3/1,
1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4, 4/1,
...と続き、
全ての正の有理数が重複なく現れる。
前の分母が次の分子になる。この数列はStern's diatomic series(スターンの二原子配列)と呼ばれる。
Stern-Brocot Tree
作り方
0.準備として左端に0/1、右端に1/0を書く。
1.「a/bとc/dの中間に(a+c)/(b+d)を書く」を繰り返す。1回目には1/1が書かれる。
2.2回目は、0/1と1/1、1/1と1/0の2ヶ所の中間に分数を書く。1/2と2/1が書かれる。
3.繰り返す。
性質
両端を除くと倍々で分数が書かれていき、
全ての正の有理数が重複なく現れる。
繰り返しの度大きさの順序が保たれ、常に左が小さく、右が大きい。
a/bとc/dがこの順に並ぶとき、ad-bc=-1