farey sequenceとは？ わかりやすく解説

数学で、ファレイ数列（ファレイすうれつ、フェアリー数列^[1]とも, Farey sequence [ˈfɛəri -]) とは、既約分数を順に並べた一群の数列であり、以下に述べるような初等整数論における興味深い性質を持つ。 正確にいえば、

自然数 n に対して、n に対応する（または、属する）ファレイ数列 (Farey sequence of order n) F_n とは、分母が n 以下で、 0 以上 1 以下の全ての既約分数を小さい順から並べてできる有限数列である。 ただし、整数 0, 1 はそれぞれ分数 0/1, 1/1 として扱われる。

定義によっては 0, 1 は数列から省かれる場合もある。 なお、英語では Farey series と呼ばれることも多いが、series（級数）の定義からいえば厳密には誤りである。

例

ファレイ数列 F_n は、具体的に n = 1, …, 8 のとき次のようになる^[2]：

F₁ = ( 0/1, 1/1)

F₂ = ( 0/1, 1/2, 1/1)

F₃ = ( 0/1, 1/3, 1/2, 2/3, 1/1)

F₄ = ( 0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1)

F₅ = ( 0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1)

F₆ = ( 0/1, 1/6, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 5/6, 1/1)

F₇ = ( 0/1, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 2/5, 3/7, 1/2, 4/7, 3/5, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 1/1)

F₈ = ( 0/1, 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8, 1/1)

性質

隣接する分数と中間数

2 つの分数 a/b と c/d が、あるファレイ数列で隣接しているならば、この 2 つの分数の間に新たな分数が加わるのは次数 b + d のファレイ数列においてであり、それは a/b, c/d の中間数（英語版）（英: mediant）と呼ばれる分数、

a + c/b + d

である。 例えば、F₅ では隣接している 1/3 と 2/5 の間に現れる最初の項は F₈ の 3/8 である。

0/1, 1/1 から中間数を繰り返し取ることによって得られる 1 から 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 以上の既約分数列を作り上げる方法を示すものであり、ファレイ数列と密接な関係がある。

連分数

ファレイ数列で隣接する分数は連分数展開と密接な関係がある。

全ての分数は最後の項が 1 となるように連分数展開を行うことができる。 例えば、 3/8 のこのような連分数展開は、

${\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]}$

フォードの円