円周率を近似できる分数

小学校で学ぶ円周率。
無限に続く循環しない小数で、既約分数で表せないということはよく知られています。
一方で、ゆとり教育において「円周率を３として計算する？」といった事が話題になりました。
実際には「3.14」が多く使われていますが、古くから分数で近似する試みも行われてきました。
そこで、分母、分子ともに整数である分数を使って円周率に近似することを考えます。

小数第n位まで円周率と一致する分数のうち、「分母が最小のもの」をπ(n)とします。
例えば、nが小さいとき、表のようになります。

小数第n位まで円周率と一致する分数のうち、分母が最小のもの

n	π(n)	分母
1	19 / 6 =3.166･･･	6
2	22 / 7 = 3.1428･･･	7
3	245 / 78 = 3.14102･･･	78

問題 n = 11のとき、π(11)の分母を求めて下さい。

参考)小数点以下11桁までの円周率は以下の通りです。
3.14159265358

考え方 3.14159265358　×　q ≠ 3.14159265359 ×　q
という式を満たすような値が見つかるまで、qを1から純に増やしていく方法が考えられます。

小数で計算すると、丸め誤差が発生する可能性があるので、整数で計算したほうがよいですね。

#!/usr/bin/awk -f

BEGIN{
    N = 11;
    q = 1;

    # 指定した桁数の円周率を整数で取得
    pi = 314159265358;
    pow = 10 ^ N;

    while (1){
        if(int(q * pi / pow) != int(q * (pi + 1) / pow)){
            # 商が一致した場合
            if(q * (pi + 1) % pow > 0){
                # 余りが0より大きいとき
                print q;
                break;
            }
        }
        q++;
    }
}

実行してみる

awk -f q12.awk 
265381

一瞬で答えが出ました