ファレイ数列
ファレイ数列で隣接する分数は連分数展開と密接な関係がある。
全ての分数は最後の項が 1 となるように連分数展開を行うことができる。 例えば、3/8 のこのような連分数展開は、
3 8 = 0 + 1 2 + 1 1 + 1 2 = 0 + 1 2 + 1 1 + 1 1 + 1 1 = [ 0 ; 2 , 1 , 1 , 1 ] {\displaystyle {\frac {3}{8}}=0+{\frac {1}{2+{\frac {1}{1+{\frac {1}{2}}}}}}=0+{\frac {1}{2+{\frac {1}{1+{\frac {1}{1+{\frac {1}{1}}}}}}}}=[0;2,1,1,1]}
となる。
一般に、もし p/q がファレイ数列 Fq で初めて現れる分数で連分数展開
[0; a1, a2, ..., an−1, an, 1]
を持つならば、Fq で p/q に隣接する 2 つの分数のうち、値として近い方の分数(これは、分母がより大きな方となる)は、連分数
[0; a1, a2, ..., an−1, an]
に展開され、もう一方の隣接する分数は、
[0; a1, a2, ..., an−1]
となる。 例えば、F8 で 3/8 = [0; 2, 1, 1, 1] に隣接する分数 2/5 と 1/3 では、2/5 の方が 3/8 に近く、連分数 [0; 2, 1, 1] に展開される。他方の 1/3 は [0; 2, 1] となる。
2 つの分数 a/b と c/d が、あるファレイ数列で隣接しているならば、この 2 つの分数の間に新たな分数が加わるのは次数 b + d のファレイ数列においてであり、それは a/b, c/d の中間数(英語版)(英: mediant)と呼ばれる分数、
a + c/b + d
である。 例えば、F5 では隣接している 1/3 と 2/5 の間に現れる最初の項は F8 の 3/8 である。
もし a/b と c/d が、あるファレイ数列でこの順で隣接するなら、その差は bc − ad/bd となるが、ファレイ数列の隣接する分数では bc−ad = 1 が成立し、差は分母の積の逆数 1/bd に等しくなる。 例えば、1/3 と 2/5 の差は 1/15 である。この逆もまた真となる。 もし 0 ≤ a/b < c/d ≤ 1 であるような負でない整数 a, c と正の整数 b, d に対し、bc − ad = 1 が成り立つならば、a/b と c/d は、max {b, d} に対応するファレイ数列において隣接する。
なお、シュターン=ブロコ木(英語版)(スターン=ブロコット木、英: Stern–Brocot tree)として知られている木構造は、0 = 0/1 と便宜的な無限大の表現 1/0 から始め、中間数を繰り返し取ることによって 0 以上の既約分数列を作り上げる方法を示すものであり、ファレイ数列と密接な関係がある。