関数型プログラミングの初級問題-30問目- 「最大公約数」

　プログラミング初心者が挑戦する関数型プログラミングによる算数の練習問題の第30問です。問題は、OCaml公式ページのものを使いました。
　内容は、問題と答案です。答案の作成時間は、約1分でした。

問題30.

　与えられた二つの自然数の最大公約数を求める関数gcdを書け。

※ 例えば、gcd 2373 3277は、113になります。

答案

本問の解き方

　最大公約数を求めるための古典的なアルゴリズム「ユークリッドの互除法」を用います。

ユークリッドの互除法
　互除法についてnoteの素敵な数式機能を使って説明します。

$$
以下、自然数aとbの最大公約数を\gcd (a, b)と表す。また、r_0 = n, r_1 = mとする。
r_0, r_1に対し、r_2 = r_0 \mod r_1とする。
r_2 = 0のとき、\gcd (r_0, r_1) = r_1である。
r_2 ≠ 0のとき、r_0 - r_1 < r_1または、r_0 - r_1 > r_1である。
r_0 - r_1 < r_1のとき、
r_0 = r_1 + r_2
であり、
\gcd (r_0, r_1) = \gcd (r_1 + r_2, r_1)
となる。さらに、r_1 + r_2 > r_1なので、最大公約数の定義より、
= \gcd (r_2, r_1)
= \gcd (r_1, r_2)
となる。
r_0 - r_1 > r_1のとき、
\exist q(1 < q \land r_0 = qr_1 + r_2)
であり、qにq_0を割り当てると、r_2 = r_0 - q_0r_1より、
\gcd (r_0, r_1) = \gcd (r_0 - r_1, r_1)
...
= \gcd (r_0 - qr_1, r_1)
= \gcd (r_2, r_1)
= \gcd (r_1, r_2)
となる。以上をまとめると、r_2 = r_0 \mod r_1とすると、
r_2 = 0のとき\gcd (r_0, r_1) = r_1
r_2 \not = 0のとき\gcd (r_0, r_1) = \gcd (r_1, r_2)
となる。さらに、r_2 \not = 0のときに、r3, ..と続けると、\modの定義よりrはだんだんと小さくなるので、あるkでr_k = 0となり、そのときr_{k-1}が最大公約数となる。この考え方が正しいことを確かめて式にすれば、OCamlのプログラムができる。
　これを示す。まず、r_iを
r_0 = n
r_1 = m
r_i = r_{i-2} \mod r_{i-1} (2 ≤ i)
とする。
　R = \{r_i \mid 2 ≤ i\}とすると、R \subset \omegaよりmin Rが存在する。r_k = min Rとして、r_k = 0を背理法により示す。
r_k \not = 0と仮定すると、
r_{k+1} = r_{k-1} \mod r_k
となるr_{k+1}が存在する。このとき、\modの定義より
r_{k+1} < r_k
であるが、これはr_k = min Rと矛盾する。
したがって、r_k = 0である。
　r_k = 0より、r_{k+1}は存在しないのでr_iは、
r_i = r_{i-2} \mod r_{i-1} (2 ≤ i ≤ k)
となる。
次に、r_i \not = 0のとき、
\gcd (r_{i-2}, r_{i-1}) = \gcd (r_{i-1}, r_i)
が成り立つことを示す。
r_i = r_{i-2} \mod r_{i-1}としたとき、r_i \not = 0なので、
r_{i-2} - r_{i-1} < r_{i-1} ∨ r_{i-2} - r_{i-1} > r_{i-1}
である。r_{i-2} - r_{i-1} < r_{i-1}のとき、
r_{i-2} - r_{i-1} = r_i
であり、r_{i-1} < r_{i-2}と最大公約数の定義より、
\gcd (r_{i-2}, r_{i-1}) = \gcd (r_{i-2} - r_{i-1}, r_{i-1})
= \gcd (r_i, r_{i-1})
= \gcd (r_{i-1}, r_i)
となる。
　r_{i-2} - r_{i-1} > r_{i-1}のとき、ある1 < qが存在して、
r_{i-2} = qr_{i-1} + r_i
である。r_{i-1} < r_{i-2}と最大公約数の定義より、
\gcd (r_{i-2}, r_{i-1}) = \gcd (r_{i-2} - r_{i-1}, r_{i-1})
である。q = 2のとき、r_{i-2} - r_{i-1} = r_{i-1}より、
= \gcd (r_{i-2} - 2r_{i-1}, r_{i-1})
= \gcd (r_i, r_{i-1})
= \gcd (r_{i-1}, r_i)
である。q \not= 2のとき、X = \{x \mid 1 < x < q \land \gcd (r_{i-2}, r_{i-1}) \not = \gcd (r_{i-2} - xr_{i-1}, r_{i-1})\}として、X \not = \emptyと仮定する。
X \subset \omegaよりp = min Xが存在する。このときp-1 \notin Xなので、
\gcd (r_{i-2}, r_{i-1}) = \gcd (r_{i-2} - (p - 1)r_{i-1}, r_{i-1})
= \gcd (r_{i-2} - pr_{i-1} + r_{i-1}, r_{i-1})
である。p < qより、r_{i-2} - pr_{i-1} > r_{i-1}なので、最大公約数の定義より、
= \gcd (r_{i-2} - pr_{i-1}, r_{i-1})
であるが、これはp \in Xと矛盾する。したがってX = \emptyである。これより、q-1について、
\gcd (r_{i-2}, r_{i-1}) = \gcd (r_{i-2} - (q-1)r_{i-1}, r_{i-1})
となり、最大公約数の定義より、
= \gcd (r_i + r_{i-1}, r_{i-1})
= \gcd (r_i, r_{i-1})
= \gcd (r_{i-1}, r_i)
となる。したがって、いずれにしても、
r_i \not = 0 \implies \gcd (r_{i-2}, r_{i-1}) = \gcd (r_{i-1}, r_i)
が成り立つ。ここで、
i ≤ k-1 \implies r_i \not = 0
なので、
\gcd (r_0, r_1) = \gcd (r_{k-2}, r_{k-1})
であり、r_{k-2} \mod r_{k-1} = r_k = 0より、
= r_{k-1}
である。
　以上をまとめると、r_i = r_{i-2} mod r_{i-1}によりr_iを順次求めていくと、あるkにてr_k = 0となり、そのときのr_{k-1}が最大公約数となる。
$$

本答案の説明
　上述の通りです。

コード

let rec gcd r1 r2 = if r2 = 0 then r1 else gcd r2 (r1 mod r2)

感想

　相変わらずnoteの表現力は素晴らしいです。
　無駄に長い長い説明を見事に一行でまとめてくれました。
　文字数の多さを感じさせることなく、それでいて全部を表示する高度な技術です。
　中学生の宿題でもなかなかこのレベルを実現できものではありません。

　無料でこのような機能が使えるのですから本当にnoteはスゴイですね。
　無料だからといってこの出来で公開するのですから本当にnoteはスゴイですね。
　もう二度と数式を書くことはないでしょう。

　次回は、第31問です。しばらく算数の問題が続きます。