[Maths] Random-Problems #10

次の分数を約分せよ。 \[ \frac{2431562551479558}{6736555210266451} \]

小さい素数から順に割ってみて、割り切れればその素因数を持つ。

• 分子 \[ \begin{align*} 2431562551479558 &= 2 \cdot 1215781275739779 \\ &= 2 \cdot 3^2 \cdot 135086808415531 \\ &= 2 \cdot 3^2 \cdot 7 \cdot 19298115487933 \\ \end{align*} \]
• 分母 \[ \begin{align*} 6736555210266451 &= 333433 \cdot 20203624747 \end{align*} \]

あまりに割れないので調べたところ、\(19298115487933\)と\(20203624747\)はクソデカ素数でした。乱数で生成した分数なので、こういうこともあります。
分母と分子に共通の因数が存在しない為、与えられた分数は既約分数であることがわかりました。

与えられた分数を連分数展開します。
具体的には、分数を次のような形に変形します。 \[ \begin{align*} a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \frac{1}{\ddots a_n}}}} \end{align*} \] 有理数であれば、途中の操作に分数が現れなくなってそこで展開が終わります。
例) \[ \begin{align*} \frac{64}{24} &= 2 + \frac{16}{24} \\ &= 2 + \frac{1}{\frac{24}{16}} \\ &= 2 + \frac{1}{1 + \frac{8}{16}} \\ &= 2 + \frac{1}{1 + \frac{1}{\frac{16}{8}}} \\ &= 2 + \frac{1}{1 + \frac{1}{2}} \\ &= 2 + \frac{2}{3} \\ &= \frac{8}{3} \end{align*} \] 分母と分子の値が小さな分数であれば素因数分解をする方が楽ですが、素因数が大きければその分発見に時間がかかります。
それに対して、連分数展開であれば「試しに割ってみる」ことはなく、記述に必要な分しか計算がないのが特徴と言えます。 \[ \begin{align*} \frac{2431562551479558}{6736555210266451} &= \frac{1}{\frac{6736555210266451}{2431562551479558}} \\ &= \frac{1}{2 + \frac{1873430107307335}{2431562551479558}} \\ &= \frac{1}{2 + \frac{1}{\frac{2431562551479558}{1873430107307335}}} \\ & \quad \vdots \\ &= \frac{1}{2 + \frac{1}{1 + \frac{1}{3 + \frac{1}{2 + \frac{1}{1 + \frac{1}{4 + \frac{1}{9 + \frac{1}{3 + \frac{1}{1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{1 + \frac{1}{5 + \frac{1}{12 + \frac{1}{2 + \frac{1}{1 + \frac{1}{1 + \frac{1}{3 + \frac{1}{2 + \frac{1}{1 + \frac{1}{1 + \frac{1}{4 + \frac{1}{1 + \frac{1}{7 + \frac{1}{1 + \frac{1}{4 + \frac{1}{1 + \frac{1}{2 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{15 + \frac{1}{1 + \frac{1}{2 + \frac{1}{5 + \frac{1}{3 + \frac{1}{1 + \frac{1}{4}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} \\ \end{align*} \] 展開が終わったら、これを戻しましょう。
すると、対象の分数が約分されているはずです。 \[ \begin{align*} & \frac{1}{2 + \frac{1}{1 + \frac{1}{3 + \frac{1}{2 + \frac{1}{1 + \frac{1}{4 + \frac{1}{9 + \frac{1}{3 + \frac{1}{1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{1 + \frac{1}{5 + \frac{1}{12 + \frac{1}{2 + \frac{1}{1 + \frac{1}{1 + \frac{1}{3 + \frac{1}{2 + \frac{1}{1 + \frac{1}{1 + \frac{1}{4 + \frac{1}{1 + \frac{1}{7 + \frac{1}{1 + \frac{1}{4 + \frac{1}{1 + \frac{1}{2 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{15 + \frac{1}{1 + \frac{1}{2 + \frac{1}{5 + \frac{1}{3 + \frac{1}{1 + \frac{1}{4}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} \\ &= \frac{1}{2 + \frac{1}{1 + \frac{1}{3 + \frac{1}{2 + \frac{1}{1 + \frac{1}{4 + \frac{1}{9 + \frac{1}{3 + \frac{1}{1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{1 + \frac{1}{5 + \frac{1}{12 + \frac{1}{2 + \frac{1}{1 + \frac{1}{1 + \frac{1}{3 + \frac{1}{2 + \frac{1}{1 + \frac{1}{1 + \frac{1}{4 + \frac{1}{1 + \frac{1}{7 + \frac{1}{1 + \frac{1}{4 + \frac{1}{1 + \frac{1}{2 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{15 + \frac{1}{1 + \frac{1}{2 + \frac{1}{5 + \frac{1}{3 + \frac{4}{4 + 1}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} \\ &= \frac{1}{2 + \frac{1}{1 + \frac{1}{3 + \frac{1}{2 + \frac{1}{1 + \frac{1}{4 + \frac{1}{9 + \frac{1}{3 + \frac{1}{1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{1 + \frac{1}{5 + \frac{1}{12 + \frac{1}{2 + \frac{1}{1 + \frac{1}{1 + \frac{1}{3 + \frac{1}{2 + \frac{1}{1 + \frac{1}{1 + \frac{1}{4 + \frac{1}{1 + \frac{1}{7 + \frac{1}{1 + \frac{1}{4 + \frac{1}{1 + \frac{1}{2 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{15 + \frac{1}{1 + \frac{1}{2 + \frac{1}{5 + \frac{1}{3 + \frac{4}{5}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} \\ & \quad \vdots \\ &= \frac{2431562551479558}{6736555210266451} \end{align*} \] Answer 1でも見せた通り、やはりこれは既約分数でした。

見せた通り、連分数はなかなかその表示の領域が大きくなってしまうことがあるので、通常は次のような表記を好みます。 \[ a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \frac{1}{\ddots a_n}}}} = [a_0; a_1, a_2, a_3, \cdots, a_n] \] 今回の問題を例にすると \[ \frac{2431562551479558}{6736555210266451} = [0; 2, 1, 3, 2, 1, 4, 9, 3, 1, 2, 2, 1, 5, 12, 2, 1, 1, 3, 2, 1, 1, 4, 1, 7, 1, 4, 1, 2, 1, 1, 1, 15, 1, 2, 5, 3, 1, 4] \] この記事を書くにあたって連分数分解をするプログラムを書いたので、最後にそれを残しておきます。

    function continuedFraction(a, b){
        if(b == 0) return void 0;
    
        let omega = [a, b];
        let result = [];
    
        while(omega[0] % omega[1] != 0){
            result.push(Math.floor(omega[0] / omega[1]));
            omega = [omega[1], omega[0] - result[result.length - 1] * omega[1]];
        }
        result.push(omega[0]/omega[1]);
    
        return result;
    } 

再帰を使うともう少し短くなります。

    function continuedFraction(a, b){
        let c = Math.floor(a/b);
        return (b == 0 ? [] : (a == 0 ? [0] : [c].concat(continuedFraction(b, a - c * b))));
    } 

    continuedFraction(2431562551479558, 6736555210266451);
    // [0, 2, 1, 3, 2, 1, 4, 9, 3, 1, 2, 2, 1, 5, 12, 2, 1, 1, 3, 2, 1, 1, 4, 1, 7, 1, 4, 1, 2, 1, 1, 1, 15, 1, 2, 5, 3, 1, 4] 

乱数で問題を作ったのは失敗でした。