ファレイ数列

ファレイ数列 - みずぴー日記 にインスパイヤされてファレイ数列を求めてみます。

ここでも同様に最大公約数 (GCD) を使った方法で求めますが、数列順には並んでいません。 また、最大公約数はユークリッドの互除法を用いて求めています。

コアとなるアルゴリズムの部分には既約分数クイズ - Maeの(Mae向きな)日記のものを使わせていただきました。(C 言語と awk なのでほぼ同じです)

#! /usr/local/bin/ngawk -f
# farey.awk
# ファレイ数列を求める
# usage: nawk -f farey.awk num

BEGIN {
    num = ARGV[1];

    printf("0/1 ");

    for (i = 1; i <= num; i++) {
        for (j = 1; j <= i; j++) {
            if (gcd(i, j) == 1) {

                printf("%d/%d ", j, i);

            }
        }
    }

    print "";
}

# gcd():    ユークリッドの互除法で最大公約数を求める
#   in:     数値 num1, num2
#   out:    数値 num1, num2 の最大公約数
function gcd(num1, num2) {
    if (num2 == 0) {

        return num1;

    } else {

        return gcd(num2, num1 % num2);

    }
}

それでは求めてみましょう。

$ nawk -f farey.awk 5
0/1 1/1 1/2 1/3 2/3 1/4 3/4 1/5 2/5 3/5 4/5 

$ nawk -f farey.awk 1
0/1 1/1 

$ nawk -f farey.awk 2
0/1 1/1 1/2 

$ nawk -f farey.awk 3
0/1 1/1 1/2 1/3 2/3 

$ nawk -f farey.awk 4
0/1 1/1 1/2 1/3 2/3 1/4 3/4 

$ nawk -f farey.awk 5
0/1 1/1 1/2 1/3 2/3 1/4 3/4 1/5 2/5 3/5 4/5 

ファレイ数列のようなものを求めるには様々な方法があるようですので、いろいろ試してみてください。 既約分数クイズに対する答えに様々な言語での実装が載っています。

tag_nawk.png tag_nawk.png tag_nawk.png tag_nawk.png