ファレイ数列

ファレイ数列とは0以上1以下の既約分数を昇順に並べて構成される数列のことである。

最大の分母 ファレイ数列
1 $\left[\displaystyle \frac{0}{1},\frac{1}{1}\right]$
2 $\displaystyle \left[\frac{0}{1},\frac{1}{2},\frac{1}{1} \right]$
3 $\displaystyle \left[\frac{0}{1},\frac{1}{3},\frac{1}{2},\frac{2}{3},\frac{1}{1}\right]$
4 $\displaystyle \left[\frac{0}{1},\frac{1}{4},\frac{1}{3},\frac{1}{2},\frac{2}{3},\frac{3}{4},\frac{1}{1}\right] $
5 $\displaystyle \left[\frac{0}{1},\frac{1}{5},\frac{1}{4},\frac{1}{3},\frac{2}{5},\frac{1}{2},\frac{3}{5},\frac{2}{3},\frac{3}{4},\frac{4}{5},\frac{1}{1}\right] $

分母が(n+1)以下のファレイ数例は、分母がn以下のファレイ数列に \[ \frac{i}{n+1} \] という形の既約分数を追加して得られるが、この新しく追加されたとなりのものを

\[\frac{a}{b},\,\frac{i}{n+1},\,\frac{c}{d}\] とおくと \[ \frac{i}{n+1} = \frac{a+c}{b+d} \] が成立する。

この事実を分母が5以下のファレイ数列を見て確認する。

\[ A = \left[\frac{0}{1},\frac{1}{5},\frac{1}{4},\frac{1}{3},\frac{2}{5},\frac{1}{2},\frac{3}{5},\frac{2}{3},\frac{3}{4},\frac{4}{5},\frac{1}{1}\right] \]

これは、分母が4以下のファレイ数列

\[ \left[\frac{0}{1},\frac{1}{4},\frac{1}{3},\frac{1}{2},\frac{2}{3},\frac{3}{4},\frac{1}{1}\right] \]

\[\frac{1}{5},\frac{2}{5},\frac{3}{5},\frac{4}{5}\]

を挿入して構成される。

数列$A$をみると$\displaystyle \frac{1}{5} $の隣の分数は$\displaystyle \frac{0}{1} $と$\displaystyle \frac{1}{4} $だから確かに

\[ \frac{1}{5} = \frac{0+1}{1+4} \]

が成立しているし、$\displaystyle \frac{2}{5} $の隣の分数をみても$\displaystyle \frac{1}{3} $と$\displaystyle \frac{1}{2} $となっていて、やはり

\[ \frac{2}{5} = \frac{1+1}{3+2} \]

が成立している。逆にこの性質を利用すると、どこにあらたな分数を挿入すべきかがわかるので、ファレイ数列の構成にも使用することができるが、以下では、定義にもどって、ファレイ数列を構成するプログラム例を見る。

必要な知識

有理数クラス の理解とLINQ。

コード

効率が良いとは言えないが、定義にしたがって、分母がn以下の0以上1以下の分数をリストに追加して、 重複要素を取り除き、順番に並べて、ファレイ数列を得る。 「有理数クラス」で作成したコード例6のクラスを使用すれば簡単。 ただし、このクラスではBigIntegerを使用しているので、using System.Numericsが必要。 これはただ記述すれば良いだけでなくて、「参照の追加」の作業が必要になる。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
class Program
{
    static void Main(string[] args)
    {
        List list = new List();
        for (int i = 1; i <= 5; i++)
        {
            for (int k = 0; k <= i; k++)
            {
                list.Add(new Rational(k, i));
            }
        }
        var farey = list.Distinct().OrderBy(x => x).ToArray();
        Console.WriteLine(string.Join(",", farey));
    }
}
//以下自作した(コード例6)の class Rational がつづく.

実行結果.

0,1/5,1/4,1/3,2/5,1/2,3/5,2/3,3/4,4/5,1