ファレイ数列のいろいろ

JOI春合宿や各種コンテスト, JJMOでたまに出題されるファレイ数列についていろいろ書きます. 面白い性質がたくさんあります.

・ファレイ数列とは？
約分された分数を昇順に並べた一群の数列であり、

正の整数 n に対して、n に対応する (または、属する、深さnの) ファレイ数列 (Farey sequence of order n) Fn とは、n 以下の分母を持つ 0 以上 1 以下のすべての約分された既約分数を昇順に並べたものである。ただし、整数 0, 1 はそれぞれ分数 0/1, 1/1 として扱われる。

定義によっては 0, 1 は数列から省かれる場合もある。

(Wikipediaより転載)

たとえば, 深さ5のファレイ数列は

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

となります.

・ファレイ数列の性質
☆a1/a2 < b1/b2が, ある深さのファレイ数列で隣り合っているとき, 深さを1ずつ増やしていくと, 最初にa1/a2とb1/b2の間に入る項は(a1 + b1) / (a2 + b2) となります.

これはファレイ数列の話の中で最も有名な性質です. (間違った分数の足し算が, ファレイ数列上では列を成すって面白いですよね!)

・深さnのファレイ数列のm番目の項
これは先ほどの性質より, 簡単な再帰呼び出しで求まります.
JOI春合宿2008年3日目の問題としてそのまま出題されています.

#include <cstdio>

using namespace std;

int m, n;
int idx;

void make(int a1, int a2, int b1, int b2)
{
	int c1 = a1 + b1, c2 = a2 + b2;
	
	if (idx > n) return;
	if (c2 > m) return;
	
	make(a1, a2, c1, c2); // a1 / a2とc1 / c2の間の項を数える
	idx++;
	
	if (idx == n){
		printf("%d %d\n", c1, c2);
		return;
	}
	
	make(c1, c2, b1, b2); // c1 / c2とb1 / b2の間の項を数える
}

int main()
{
	scanf("%d %d", &m, &n);
	
	make(0, 1, 1, 1); // ファレイ数列の各項は0 / 1( = 0)と1 / 1( = 1)の間に存在する.
	
	if (idx < n) printf("-1\n");
	
	return (0);
}

・深さkのファレイ数列の項数

これもコンテストで出題されました.

深さkのファレイ数列の項数は, Σ[i = 2...k]i以下でと互いに素な数 (+ 2 (0/1 と 1/1を含める場合))となります.
iを超える数であれば, 1以上の数になってしまいます.
また, iと互いに素でなければ, その項は約分して数列上の別の項にできます.
したがって, 上記の条件を満たすものが項数となります.
これは, オイラーのφ関数で高速に求めることができます.

#include <cstdio>
#include <cstring>
 
#define MAX (1000000)
 
using namespace std;
 
typedef long long lint;
 
int eulerPhi(int n) {
    int ans;
    int x;
    if (n == 0){
        return (0);
    }
    ans = n;
    for (x = 2; x * x <= n; ++x){
        if (n % x == 0) {
            ans -= ans / x;
            while (n % x == 0){
                n /= x;
            }
        }
    }
    if (n > 1){
        ans -= ans / n;
    }
    return (ans);
}
int main(void)
{
    int n, m;
    int i, j;
    static lint euler[MAX + 1];
     
    for (i = 1; i <= MAX; i++){
        euler[i] = eulerPhi(i);
    }
     
    for (i = 1; i <= MAX; i++){
        euler[i] += euler[i - 1];
    }
     
    scanf("%d", &n);
     
    for (i = 0; i < n; i++){
        scanf("%d", &m);
        printf("%lld\n", euler[m] + 1);
    }
     
    return (0);
}

・さらなる性質
☆2つの既約分数a1/a2 < b1/b2がある深さのファレイ数列において隣り合うのは, a2b1 - a1b2 = 1のときで、その時に限ります.
上で述べた性質と組み合わせると,
☆a2b1 - a1b2 = 1であるとき,
a1/a2 < p/q < b1/b2 となるすべての既約分数は, 正の整数s, tを用いて(a1s + b1t)/(a2s + b2t) の形であらわせることがわかります.

[参考:ジュニア数学オリンピック2006-2010, 数学オリンピック財団]

Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

ファレイ数列のいろいろ