Processing math: 100%

[Maths] Random-Problems #10

Maths random-problems

t f B! P L

Problem

次の分数を約分せよ。 24315625514795586736555210266451

Answer 1 (気合で素因数分解)

小さい素数から順に割ってみて、割り切れればその素因数を持つ。
  • 分子 2431562551479558=21215781275739779=232135086808415531=232719298115487933
  • 分母 6736555210266451=33343320203624747
あまりに割れないので調べたところ、1929811548793320203624747はクソデカ素数でした。乱数で生成した分数なので、こういうこともあります。
分母と分子に共通の因数が存在しない為、与えられた分数は既約分数であることがわかりました。

Answer 2 (連分数展開)

与えられた分数を連分数展開します。
具体的には、分数を次のような形に変形します。 a0+1a1+1a2+1a3+1an 有理数であれば、途中の操作に分数が現れなくなってそこで展開が終わります。
例) 6424=2+1624=2+12416=2+11+816=2+11+1168=2+11+12=2+23=83 分母と分子の値が小さな分数であれば素因数分解をする方が楽ですが、素因数が大きければその分発見に時間がかかります。
それに対して、連分数展開であれば「試しに割ってみる」ことはなく、記述に必要な分しか計算がないのが特徴と言えます。 24315625514795586736555210266451=167365552102664512431562551479558=12+18734301073073352431562551479558=12+124315625514795581873430107307335=12+11+13+12+11+14+19+13+11+12+12+11+15+112+12+11+11+13+12+11+11+14+11+17+11+14+11+12+11+11+11+115+11+12+15+13+11+14 展開が終わったら、これを戻しましょう。
すると、対象の分数が約分されているはずです。 12+11+13+12+11+14+19+13+11+12+12+11+15+112+12+11+11+13+12+11+11+14+11+17+11+14+11+12+11+11+11+115+11+12+15+13+11+14=12+11+13+12+11+14+19+13+11+12+12+11+15+112+12+11+11+13+12+11+11+14+11+17+11+14+11+12+11+11+11+115+11+12+15+13+44+1=12+11+13+12+11+14+19+13+11+12+12+11+15+112+12+11+11+13+12+11+11+14+11+17+11+14+11+12+11+11+11+115+11+12+15+13+45=24315625514795586736555210266451 Answer 1でも見せた通り、やはりこれは既約分数でした。
見せた通り、連分数はなかなかその表示の領域が大きくなってしまうことがあるので、通常は次のような表記を好みます。 a0+1a1+1a2+1a3+1an=[a0;a1,a2,a3,,an] 今回の問題を例にすると 24315625514795586736555210266451=[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] この記事を書くにあたって連分数分解をするプログラムを書いたので、最後にそれを残しておきます。
  1. function continuedFraction(a, b){
  2. if(b == 0) return void 0;
  3. let omega = [a, b];
  4. let result = [];
  5. while(omega[0] % omega[1] != 0){
  6. result.push(Math.floor(omega[0] / omega[1]));
  7. omega = [omega[1], omega[0] - result[result.length - 1] * omega[1]];
  8. }
  9. result.push(omega[0]/omega[1]);
  10. return result;
  11. }

再帰を使うともう少し短くなります。
  1. function continuedFraction(a, b){
  2. let c = Math.floor(a/b);
  3. return (b == 0 ? [] : (a == 0 ? [0] : [c].concat(continuedFraction(b, a - c * b))));
  4. }

  1. continuedFraction(2431562551479558, 6736555210266451);
  2. // [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]

End

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

Contributor

ゆっくり勉強ちゃんねる
  • YouTube
  • X (Twitter)
  • niconico
  • TikTok
  • QooQ